HyperLib 1997 Winter - Disc 1/HYPERLIB-1997-Winter-CD1.ISO.7z/HYPERLIB-1997-Winter-CD1.ISO/オンラインウェア/PRG/PL 2.0 SupplementDoc Folder.sit/PL 2.0 SupplementDoc Folder/Documentation/Chapter 07. Control Structure

Text File | 1995-03-27 | 175KB | 4,007 lines

Common Lisp the Language, 2nd Edition
-------------------------------------------------------------------------------

7. Control Structure

Common Lisp provides a variety of special structures for organizing programs.
Some have to do with flow of control (control structures), while others control
access to variables (environment structures). Some of these features are
implemented as special forms; others are implemented as macros, which typically
expand into complex program fragments expressed in terms of special forms or
other macros.

Function application is the primary method for construction of Lisp programs.
Operations are written as the application of a function to its arguments.
Usually, Lisp programs are written as a large collection of small functions,
each of which implements a simple operation. These functions operate by calling
one another, and so larger operations are defined in terms of smaller ones.
Lisp functions may call upon themselves recursively, either directly or
indirectly.

[change_begin]
Locally defined functions (flet, labels) and macros (macrolet) are quite
versatile. The new symbol macro facility allows even more syntactic
flexibility.
[change_end]

While the Lisp language is more applicative in style than statement-oriented,
it nevertheless provides many operations that produce side effects and
consequently requires constructs for controlling the sequencing of side
effects. The construct progn, which is roughly equivalent to an Algol begin-end
block with all its semicolons, executes a number of forms sequentially,
discarding the values of all but the last. Many Lisp control constructs include
sequencing implicitly, in which case they are said to provide an ``implicit
progn.''   Other sequencing constructs include prog1 and prog2.

For looping, Common Lisp provides the general iteration facility do as well as
a variety of special-purpose iteration facilities for iterating or mapping over
various data structures.

Common Lisp provides the simple one-way conditionals when and unless, the
simple two-way conditional if, and the more general multi-way conditionals such
as cond and case. The choice of which form to use in any particular situation
is a matter of taste and style.

Constructs for performing non-local exits with various scoping disciplines are
provided: block, return, return-from, catch, and throw.

The multiple-value constructs provide an efficient way for a function to return
more than one value; see values.

-------------------------------------------------------------------------------

   *  Constants and Variables
        o  Reference
        o  Assignment
   *  Generalized Variables
   *  Function Invocation
   *  Simple Sequencing
   *  Establishing New Variable Bindings
   *  Conditionals
   *  Blocks and Exits
   *  Iteration
        o  Indefinite Iteration
        o  General Iteration
        o  Simple Iteration Constructs
        o  Mapping
        o  The ``Program Feature''
   *  Structure Traversal and Side Effects
   *  Multiple Values
        o  Constructs for Handling Multiple Values
        o  Rules Governing the Passing of Multiple Values
   *  Dynamic Non-Local Exits

-------------------------------------------------------------------------------

7.1. Constants and Variables

Because some Lisp data objects are used to represent programs, one cannot
always notate a constant data object in a program simply by writing the
notation for the object unadorned; it would be ambiguous whether a constant
object or a program fragment was intended. The quote special form resolves this
ambiguity.

There are two kinds of variables in Common Lisp, in effect: ordinary variables
and function names. There are some similarities between the two kinds, and in a
few cases there are similar functions for dealing with them, for example boundp
and fboundp. However, for the most part the two kinds of variables are used for
very different purposes: one to name defined functions, macros, and special
forms, and the other to name data objects.

[change_begin]
X3J13 voted in March 1989 (FUNCTION-NAME)   to introduce the concept of a
function-name, which may be either a symbol or a two-element list whose first
element is the symbol setf and whose second element is a symbol. The primary
purpose of this is to allow setf expander functions to be CLOS generic
functions with user-defined methods. Many places in Common Lisp that used to
require a symbol for a function name are changed to allow 2-lists as well; for
example, defun is changed so that one may write (defun (setf foo) ...), and the
function special form is changed to accept any function-name. See also
fdefinition.

By convention, any function named (setf f) should return its first argument as
its only value, in order to preserve the specification that setf returns its
newvalue. See setf.

Implementations are free to extend the syntax of function-names to include
lists beginning with additional symbols other than setf or lambda.
[change_end]

-------------------------------------------------------------------------------

   *  Reference
   *  Assignment

-------------------------------------------------------------------------------

7.1. Reference

The value of an ordinary variable may be obtained simply by writing the name of
the variable as a form to be executed. Whether this is treated as the name of a
special variable or a lexical variable is determined by the presence or absence
of an applicable special declaration; see chapter 9.

The following functions and special forms allow reference to the values of
constants and variables in other ways.

[Special Form]
quote object

(quote x) simply returns x. The object is not evaluated and may be any Lisp
object whatsoever. This construct allows any Lisp object to be written as a
constant value in a program. For example:

(setq a 43)
(list a (cons a 3)) => (43 (43 . 3))
(list (quote a) (quote (cons a 3)) => (a (cons a 3))

Since quote forms are so frequently useful but somewhat cumbersome to type, a
standard abbreviation is defined for them: any form f preceded by a single
quote (') character is assumed to have (quote ) wrapped around it to make
(quote f). For example:

(setq x '(the magic quote hack))

is normally interpreted by read to mean

(setq x (quote (the magic quote hack)))

See section 22.1.3.

[change_begin]
X3J13 voted in January 1989 (CONSTANT-MODIFICATION)   to clarify that it is an
error to destructively modify any object that appears as a constant in
executable code, whether within a quote special form or as a self-evaluating
form.

See section 25.1 for a discussion of how quoted constants are treated by the
compiler.

X3J13 voted in March 1989 (QUOTE-SEMANTICS)   to clarify that eval and compile
are not permitted either to copy or to coalesce (``collapse'') constants (see
eq) appearing in the code they process; the resulting program behavior must
refer to objects that are eql to the corresponding objects in the source code.
Moreover, the constraints introduced by the votes on issues
(CONSTANT-COMPILABLE-TYPES)   and (CONSTANT-CIRCULAR-COMPILATION)   on what
kinds of objects may appear as constants apply only to compile-file (see
section 25.1).
[change_end]

[Special Form]
function fn

The value of function is always the functional interpretation of fn; fn is
interpreted as if it had appeared in the functional position of a function
invocation. In particular, if fn is a symbol, the functional definition
associated with that symbol is returned; see symbol-function. If fn is a
lambda-expression, then a ``lexical closure'' is returned, that is, a function
that when invoked will execute the body of the lambda-expression in such a way
as to observe the rules of lexical scoping properly.

[change_begin]
X3J13 voted in June 1988 (FUNCTION-TYPE)   to specify that the result of a
function special form is always of type function. This implies that a form
(function fn) may be interpreted as (the (function fn)).

It is an error to use the function special form on a symbol that does not
denote a function in the lexical or global environment in which the special
form appears. Specifically, it is an error to use the function special form on
a symbol that denotes a macro or special form. Some implementations may choose
not to signal this error for performance reasons, but implementations are
forbidden to extend the semantics of function in this respect; that is, an
implementation is not allowed to define the failure to signal an error to be a
``useful'' behavior.

X3J13 voted in March 1989 (FUNCTION-NAME)   to extend function to accept any
function-name (a symbol or a list whose car is setf-see section 7.1) as well as
lambda-expressions. Thus one may write (function (setf cadr)) to refer to the
setf expansion function for cadr.
[change_end]

  For example:

(defun adder (x) (function (lambda (y) (+ x y))))

The result of (adder 3) is a function that will add 3 to its argument:

(setq add3 (adder 3))
(funcall add3 5) => 8

This works because function creates a closure of the inner lambda-expression
that is able to refer to the value 3 of the variable x even after control has
returned from the function adder.

More generally, a lexical closure in effect retains the ability to refer to
lexically visible bindings, not just values. Consider this code:

(defun two-funs (x)
  (list (function (lambda () x))
        (function (lambda (y) (setq x y)))))
(setq funs (two-funs 6))
(funcall (car funs)) => 6
(funcall (cadr funs) 43) => 43
(funcall (car funs)) => 43

The function two-funs returns a list of two functions, each of which refers to
the binding of the variable x created on entry to the function two-funs when it
was called with argument 6. This binding has the value 6 initially, but setq
can alter a binding. The lexical closure created for the first
lambda-expression does not ``snapshot'' the value 6 for x when the closure is
created. The second function can be used to alter the binding (to 43, in the
example), and this altered value then becomes accessible to the first function.

In situations where a closure of a lambda-expression over the same set of
bindings may be produced more than once, the various resulting closures may or
may not be eq, at the discretion of the implementation. For example:

(let ((x 5) (funs '()))
  (dotimes (j 10)
    (push #'(lambda (z)
              (if (null z) (setq x 0) (+ x z)))
          funs))
  funs)

The result of the above expression is a list of ten closures. Each logically
requires only the binding of x. It is the same binding in each case, so the ten
closures may or may not be the same identical (eq) object. On the other hand,
the result of the expression

(let ((funs '()))
  (dotimes (j 10)
    (let ((x 5))
      (push (function (lambda (z)
                        (if (null z) (setq x 0) (+ x z))))
            funs)))
  funs)

is also a list of ten closures. However, in this case no two of the closures
may be eq, because each closure is over a distinct binding of x, and these
bindings can be behaviorally distinguished because of the use of setq.

The question of distinguishable behavior is important; the result of the
simpler expression

(let ((funs '()))
  (dotimes (j 10)
    (let ((x 5))
      (push (function (lambda (z) (+ x z)))
            funs)))
  funs)

is a list of ten closures that may be pairwise eq. Although one might think
that a different binding of x is involved for each closure (which is indeed the
case), the bindings cannot be distinguished because their values are identical
and immutable, there being no occurrence of setq on x. A compiler would
therefore be justified in transforming the expression to

(let ((funs '()))
  (dotimes (j 10)
    (push (function (lambda (z) (+ 5 z)))
          funs))
  funs)

where clearly the closures may be the same after all. The general rule, then,
is that the implementation is free to have two distinct evaluations of the same
function form produce identical (eq) closures if it can prove that the two
conceptually distinct resulting closures must in fact be behaviorally identical
with respect to invocation. This is merely a permitted optimization; a
perfectly valid implementation might simply cause every distinct evaluation of
a function form to produce a new closure object not eq to any other.

Frequently a compiler can deduce that a closure in fact does not need to close
over any variable bindings. For example, in the code fragment

(mapcar (function (lambda (x) (+ x 2))) y)

the function (lambda (x) (+ x 2)) contains no references to any outside entity.
In this important special case, the same ``closure'' may be used as the value
for all evaluations of the function special form. Indeed, this value need not
be a closure object at all; it may be a simple compiled function containing no
environment information. This example is simply a special case of the foregoing
discussion and is included as a hint to implementors familiar with previous
methods of implementing Lisp. The distinction between closures and other kinds
of functions is somewhat pointless, actually, as Common Lisp defines no
particular representation for closures and no way to distinguish between
closures and non-closure functions. All that matters is that the rules of
lexical scoping be obeyed.

Since function forms are so frequently useful but somewhat cumbersome to type,
a standard abbreviation is defined for them: any form f preceded by #' (#
followed by an apostrophe) is assumed to have (function ) wrapped around it to
make (function f). For example,

(remove-if #'numberp '(1 a b 3))

is normally interpreted by read to mean

(remove-if (function numberp) '(1 a b 3))

See section 22.1.4.

[Function]
symbol-value symbol

symbol-value returns the current value of the dynamic (special) variable named
by symbol. An error occurs if the symbol has no value; see boundp and
makunbound. Note that constant symbols are really variables that cannot be
changed, and so symbol-value may be used to get the value of a named constant.
In particular, symbol-value of a keyword will return that keyword.

symbol-value cannot access the value of a lexical variable.

This function is particularly useful for implementing interpreters for
languages embedded in Lisp. The corresponding assignment primitive is set;
alternatively, symbol-value may be used with setf.

[Function]
symbol-function symbol

symbol-function returns the current global function definition named by symbol.
An error is signalled if the symbol has no function definition; see fboundp.
Note that the definition may be a function or may be an object representing a
special form or macro. In the latter case, however, it is an error to attempt
to invoke the object as a function. If it is desired to process macros, special
forms, and functions equally well, as when writing an interpreter, it is best
first to test the symbol with macro-function and special-form-p and then to
invoke the functional value only if these two tests both yield false.

This function is particularly useful for implementing interpreters for
languages embedded in Lisp.

symbol-function cannot access the value of a lexical function name produced by
flet or labels; it can access only the global function value.

The global function definition of a symbol may be altered by using setf with
symbol-function. Performing this operation causes the symbol to have only the
specified definition as its global function definition; any previous
definition, whether as a macro or as a function, is lost. It is an error to
attempt to redefine the name of a special form (see table 5-1).

[change_begin]
X3J13 voted in June 1988 (FUNCTION-TYPE)   to clarify the behavior of
symbol-function in the light of the redefinition of the type function.

   *  It is permissible to call symbol-function on any symbol for which fboundp
     returns true. Note that fboundp must return true for a symbol naming a
     macro or a special form.

   *  If fboundp returns true for a symbol but the symbol denotes a macro or
     special form, then the value returned by symbol-function is not
     well-defined but symbol-function will not signal an error.

   *  When symbol-function is used with setf the new value must be of type
     function. It is an error to set the symbol-function of a symbol to a
     symbol, a list, or the value returned by symbol-function on the name of a
     macro or a special form.

[change_end]

[change_begin]

[Function]
fdefinition function-name

X3J13 voted in March 1989 (FUNCTION-NAME)   to add the function fdefinition to
the language. It is exactly like symbol-function except that its argument may
be any function-name (a symbol or a list whose car is setf-see section 7.1); it
returns the current global function definition named by the argument
function-name. One may use fdefinition with setf to change the current global
function definition associated with a function-name.
[change_end]

[Function]
boundp symbol

boundp is true if the dynamic (special) variable named by symbol has a value;
otherwise, it returns nil.

See also set and makunbound.

[Function]
fboundp symbol

fboundp is true if the symbol has a global function definition. Note that
fboundp is true when the symbol names a special form or macro. macro-function
and special-form-p may be used to test for these cases.

[change_begin]
X3J13 voted in June 1988 (FUNCTION-TYPE)   to emphasize that, despite the
tightening of the definition of the type function, fboundp must return true
when the argument names a special form or macro.

See also symbol-function and fmakunbound.

X3J13 voted in March 1989 (FUNCTION-NAME)   to extend fboundp to accept any
function-name (a symbol or a list whose car is setf-see section 7.1). Thus one
may write (fboundp '(setf cadr)) to determine whether a setf expansion function
has been globally defined for cadr.
[change_end]

[Function]
special-form-p symbol

The function special-form-p takes a symbol. If the symbol globally names a
special form, then a non-nil value is returned; otherwise nil is returned. A
returned non-nil value is typically a function of implementation-dependent
nature that can be used to interpret (evaluate) the special form.

It is possible for both special-form-p and macro-function to be true of a
symbol. This is possible because an implementation is permitted to implement
any macro also as a special form for speed. On the other hand, the macro
definition must be available for use by programs that understand only the
standard special forms listed in table 5-1.

-------------------------------------------------------------------------------

7.1.2. Assignment

The following facilities allow the value of a variable (more specifically, the
value associated with the current binding of the variable) to be altered. Such
alteration is different from establishing a new binding. Constructs for
establishing new bindings of variables are described in section 7.5.

[Special Form]
setq {var form}*

The special form (setq var1 form1 var2 form2 ...) is the ``simple variable
assignment statement'' of Lisp. First form1 is evaluated and the result is
stored in the variable var1, then form2 is evaluated and the result stored in
var2, and so forth. The variables are represented as symbols, of course, and
are interpreted as referring to static or dynamic instances according to the
usual rules. Therefore setq may be used for assignment of both lexical and
special variables.

setq returns the last value assigned, that is, the result of the evaluation of
its last argument. As a boundary case, the form (setq) is legal and returns
nil. There must be an even number of argument forms. For example, in

(setq x (+ 3 2 1) y (cons x nil))

x is set to 6, y is set to (6), and the setq returns (6). Note that the first
assignment is performed before the second form is evaluated, allowing that form
to use the new value of x.

See also the description of setf, the Common Lisp ``general assignment
statement'' that is capable of assigning to variables, array elements, and
other locations.

[change_begin]
Some programmers choose to avoid setq as a matter of style, always using setf
for any kind of structure modification. Others use setq with simple variable
names and setf with all other generalized variables.

X3J13 voted in March 1989 (SYMBOL-MACROLET-SEMANTICS)   to specify that if any
var refers not to an ordinary variable but to a binding made by
symbol-macrolet, then that var is handled as if setf had been used instead of
setq.
[change_end]

[Macro]
psetq {var form}*

A psetq form is just like a setq form, except that the assignments happen in
parallel. First all of the forms are evaluated, and then the variables are set
to the resulting values. The value of the psetq form is nil. For example:

(setq a 1)
(setq b 2)
(psetq a b  b a)
a => 2
b => 1

In this example, the values of a and b are exchanged by using parallel
assignment. (If several variables are to be assigned in parallel in the context
of a loop, the do construct may be appropriate.)

See also the description of psetf, the Common Lisp ``general parallel
assignment statement'' that is capable of assigning to variables, array
elements, and other locations.

[change_begin]
X3J13 voted in March 1989 (SYMBOL-MACROLET-SEMANTICS)   to specify that if any
var refers not to an ordinary variable but to a binding made by
symbol-macrolet, then that var is handled as if psetf had been used instead of
psetq.
[change_end]

[Function]
set symbol value

set allows alteration of the value of a dynamic (special) variable. set causes
the dynamic variable named by symbol to take on value as its value.

[change_begin]
X3J13 voted in January 1989 (ARGUMENTS-UNDERSPECIFIED)   to clarify that the
value may be any Lisp datum whatsoever.
[change_end]

Only the value of the current dynamic binding is altered; if there are no
bindings in effect, the most global value is altered. For example,

(set (if (eq a b) 'c 'd) 'foo)

will either set c to foo or set d to foo, depending on the outcome of the test
(eq a b).

set returns value as its result.

set cannot alter the value of a local (lexically bound) variable. The special
form setq is usually used for altering the values of variables (lexical or
dynamic) in programs. set is particularly useful for implementing interpreters
for languages embedded in Lisp. See also progv, a construct that performs
binding rather than assignment of dynamic variables.

[Function]
makunbound symbol
fmakunbound symbol

makunbound causes the dynamic (special) variable named by symbol to become
unbound (have no value). fmakunbound does the analogous thing for the global
function definition named by symbol. For example:

(setq a 1)
a => 1
(makunbound 'a)
a => causes an error

(defun foo (x) (+ x 1))
(foo 4) => 5
(fmakunbound 'foo)
(foo 4) => causes an error

Both functions return symbol as the result value.

[change_begin]
X3J13 voted in March 1989 (FUNCTION-NAME)   to extend fmakunbound to accept any
function-name (a symbol or a list whose car is setf - see section 7.1). Thus
one may write (fmakunbound '(setf cadr)) to remove any global definition of a
setf expansion function for cadr.
[change_end]

-------------------------------------------------------------------------------

7.2. Generalized Variables

In Lisp, a variable can remember one piece of data, that is, one Lisp object.
The main operations on a variable are to recover that object and to alter the
variable to remember a new object; these operations are often called access and
update operations. The concept of variables named by symbols can be generalized
to any storage location that can remember one piece of data, no matter how that
location is named. Examples of such storage locations are the car and cdr of a
cons, elements of an array, and components of a structure.

For each kind of generalized variable, typically there are two functions that
implement the conceptual access and update operations. For a variable, merely
mentioning the name of the variable accesses it, while the setq special form
can be used to update it. The function car accesses the car of a cons, and the
function rplaca updates it. The function symbol-value accesses the dynamic
value of a variable named by a given symbol, and the function set updates it.

Rather than thinking about two distinct functions that respectively access and
update a storage location somehow deduced from their arguments, we can instead
simply think of a call to the access function with given arguments as a name
for the storage location. Thus, just as x may be considered a name for a
storage location (a variable), so (car x) is a name for the car of some cons
(which is in turn named by x). Now, rather than having to remember two
functions for each kind of generalized variable (having to remember, for
example, that rplaca corresponds to car), we adopt a uniform syntax for
updating storage locations named in this way, using the setf macro. This is
analogous to the way we use the setq special form to convert the name of a
variable (which is also a form that accesses it) into a form that updates it.
The uniformity of this approach is illustrated in the following table.

Access Function     Update Function      Update Using setf
----------------------------------------------------------------------
x                   (setq x datum)       (setf x datum)
(car x)             (rplaca x datum)     (setf (car x) datum)
(symbol-value x)    (set x datum)        (setf (symbol-value x) datum)
----------------------------------------------------------------------

setf is actually a macro that examines an access form and produces a call to
the corresponding update function.

Given the existence of setf in Common Lisp, it is not necessary to have setq,
rplaca, and set; they are redundant. They are retained in Common Lisp because
of their historical importance in Lisp. However, most other update functions
(such as putprop, the update function for get) have been eliminated from Common
Lisp in the expectation that setf will be uniformly used in their place.

[Macro]
setf {place newvalue}*

(setf place newvalue) takes a form place that when evaluated accesses a data
object in some location and ``inverts'' it to produce a corresponding form to
update the location. A call to the setf macro therefore expands into an update
form that stores the result of evaluating the form newvalue into the place
referred to by the access form.

If more than one place-newvalue pair is specified, the pairs are processed
sequentially; that is,

(setf place1 newvalue1
      place2 newvalue2)
      ...
      placen newvaluen)

is precisely equivalent to

(progn (setf place1 newvalue1)
       (setf place2 newvalue2)
       ...
       (setf placen newvaluen))

For consistency, it is legal to write (setf), which simply returns nil.

The form place may be any one of the following:

   *  The name of a variable (either lexical or dynamic).

   *  A function call form whose first element is the name of any one of the
     following functions:

     aref        car        svref
     nth         cdr        get
     elt         caar       getf             symbol-value
     rest        cadr       gethash          symbol-function
     first       cdar       documentation    symbol-plist
     second      cddr       fill-pointer     macro-function
     third       caaar      caaaar           cdaaar
     fourth      caadr      caaadr           cdaadr
     fifth       cadar      caadar           cdadar
     sixth       caddr      caaddr           cdaddr
     seventh     cdaar      cadaar           cddaar
     eighth      cdadr      cadadr           cddadr
     ninth       cddar      caddar           cdddar
     tenth       cdddr      cadddr           cddddr

[change_begin]

     X3J13 voted in March 1988 (AREF-1D)   to add row-major-aref to this list.

     X3J13 voted in June 1989 (DEFINE-COMPILER-MACRO)   to add
     compiler-macro-function to this list.

     X3J13 voted in March 1989 (FUNCTION-NAME)   to clarify that this rule
     applies only when the function name refers to a global function definition
     and not to a locally defined function or macro.

[change_end]

   *  A function call form whose first element is the name of a selector
     function constructed by defstruct.

[change_begin]

     X3J13 voted in March 1989 (FUNCTION-NAME)   to clarify that this rule
     applies only when the function name refers to a global function definition
     and not to a locally defined function or macro.

[change_end]

   *  A function call form whose first element is the name of any one of the
     following functions, provided that the new value is of the specified type
     so that it can be used to replace the specified ``location'' (which is in
     each of these cases not truly a generalized variable):

     Function Name   Required Type
     --------------------------------
     char    string-char
     schar   string-char
     bit     bit
     sbit    bit
     subseq  sequence
     --------------------------------

[change_begin]

     X3J13 voted in March 1989 (CHARACTER-PROPOSAL)   to eliminate the type
     string-char and to redefine string to be the union of one or more
     specialized vector types, the types of whose elements are subtypes of the
     type character. In the preceding table, the type string-char should be
     replaced by some such phrase as ``the element-type of the argument
     vector.''

     X3J13 voted in March 1989 (FUNCTION-NAME)   to clarify that this rule
     applies only when the function name refers to a global function definition
     and not to a locally defined function or macro.

[change_end]

     In the case of subseq, the replacement value must be a sequence whose
     elements may be contained by the sequence argument to subseq. (Note that
     this is not so stringent as to require that the replacement value be a
     sequence of the same type as the sequence of which the subsequence is
     specified.) If the length of the replacement value does not equal the
     length of the subsequence to be replaced, then the shorter length
     determines the number of elements to be stored, as for the function
     replace.

   *  A function call form whose first element is the name of any one of the
     following functions, provided that the specified argument to that function
     is in turn a place form; in this case the new place has stored back into
     it the result of applying the specified ``update'' function (which is in
     each of these cases not a true update function):

     Function Name   Argument That Is a place    Update Function Used
     ----------------------------------------------------------------
     char-bit        first                       set-char-bit
     ldb             second                      dpb
     mask-field      second                      deposit-field
     ----------------------------------------------------------------

[change_begin]

     X3J13 voted in March 1989 (CHARACTER-PROPOSAL)   to eliminate char-bit and
     set-char-bit.

     X3J13 voted in March 1989 (FUNCTION-NAME)   to clarify that this rule
     applies only when the function name refers to a global function definition
     and not to a locally defined function or macro.

[change_end]

   *  A the type declaration form, in which case the declaration is transferred
     to the newvalue form, and the resulting setf form is analyzed. For
     example,

     (setf (the integer (cadr x)) (+ y 3))

     is processed as if it were

     (setf (cadr x) (the integer (+ y 3)))

   *  A call to apply where the first argument form is of the form #'name, that
     is, (function name), where name is the name of a function, calls to which
     are recognized as places by setf. Suppose that the use of setf with apply
     looks like this:

     (setf (apply #'name x1 x2 ... xn rest) x0)

     The setf method for the function name must be such that

     (setf (name z1 z2 ... zm) z0)

     expands into a store form

     (storefn zi   zi   ... zi   zm)

     That is, it must expand into a function call such that all arguments but
     the last may be any permutation or subset of the new value z0 and the
     arguments of the access form, but the last argument of the storing call
     must be the same as the last argument of the access call. See
     define-setf-method for more details on accessing and storing forms.

     Given this, the setf-of-apply form shown above expands into

     (apply #'storefn xi   xi   ... xi   rest)

     As an example, suppose that the variable indexes contains a list of
     subscripts for a multidimensional array foo whose rank is not known until
     run time. One may access the indicated element of the array by writing

     (apply #'aref foo indexes)

     and one may alter the value of the indicated element to that of newvalue
     by writing

     (setf (apply #'aref foo indexes) newvalue)

[change_begin]

     X3J13 voted in March 1989 (FUNCTION-NAME)   to clarify that this rule
     applies only when the function name apply refers to the global function
     definition and not to a locally defined function or macro named apply.

[change_end]

   *  A macro call, in which case setf expands the macro call and then analyzes
     the resulting form.

[change_begin]

     X3J13 voted in March 1989 (FUNCTION-NAME)   to clarify that this step uses
     macroexpand-1, not macroexpand. This allows the chance to apply any of the
     rules preceding this one to any of the intermediate expansions.

[change_end]

   *  Any form for which a defsetf or define-setf-method declaration has been
     made.

[change_begin]

     X3J13 voted in March 1989 (FUNCTION-NAME)   to clarify that this rule
     applies only when the function name in the form refers to a global
     function definition and not to a locally defined function or macro.

X3J13 voted in March 1989 (FUNCTION-NAME)   to add one more rule to the
preceding list, coming after all those listed above:

   *  Any other list whose first element is a symbol (call it f). In this case,
     the call to setf expands into a call to the function named by the list
     (setf f) (see section 7.1). The first argument is the new value and the
     remaining arguments are the values of the remaining elements of place.
     This expansion occurs regardless of whether either f or (setf f) is
     defined as a function locally, globally, or not at all. For example,

     (setf (f arg1 arg2 ...) newvalue)

     expands into a form with the same effect and value as

     (let ((#:temp1 arg1)     ;Force correct order of evaluation
           (#:temp2 arg2)
           ...
           (#:temp0 newvalue))
       (funcall (function (setf f))
                #:temp0
                #:temp1
                #:temp2 ...))

     By convention, any function named (setf f) should return its first
     argument as its only value, in order to preserve the specification that
     setf returns its newvalue.

X3J13 voted in March 1989 (SYMBOL-MACROLET-SEMANTICS)   to add this case as
well:

   *  A variable reference that refers to a symbol macro definition made by
     symbol-macrolet, in which case setf expands the reference and then
     analyzes the resulting form.

[change_end]

setf carefully arranges to preserve the usual left-to-right order in which the
various subforms are evaluated. On the other hand, the exact expansion for any
particular form is not guaranteed and may even be implementation-dependent; all
that is guaranteed is that the expansion of a setf form will be an update form
that works for that particular implementation, and that the left-to-right
evaluation of subforms is preserved.

The ultimate result of evaluating a setf form is the value of newvalue.
Therefore (setf (car x) y) does not expand into precisely (rplaca x y), but
into something more like

(let ((G1 x) (G2 y)) (rplaca G1 G2) G2)

the precise expansion being implementation-dependent.

The user can define new setf expansions by using defsetf.

[change_begin]
X3J13 voted in June 1989 (SETF-MULTIPLE-STORE-VARIABLES)   to extend the
specification of setf to allow a place whose setf method has more than one
store variable (see define-setf-method). In such a case as many values are
accepted from the newvalue form as there are store variables; extra values are
ignored and missing values default to nil, as is usual in situations involving
multiple values.

A proposal was submitted to X3J13 in September 1989 to add a setf method for
values so that one could in fact write, for example,

(setf (values quotient remainder)
      (truncate linewidth tabstop))

but unless this proposal is accepted users will have to define a setf method
for values themselves (not a difficult task).
[change_end]

[Macro]
psetf {place newvalue}*

psetf is like setf except that if more than one place-newvalue pair is
specified, then the assignments of new values to places are done in parallel.
More precisely, all subforms that are to be evaluated are evaluated from left
to right; after all evaluations have been performed, all of the assignments are
performed in an unpredictable order. (The unpredictability matters only if more
than one place form refers to the same place.) psetf always returns nil.

[change_begin]
X3J13 voted in June 1989 (SETF-MULTIPLE-STORE-VARIABLES)   to extend the
specification of psetf to allow a place whose setf method has more than one
store variable (see define-setf-method). In such a case as many values are
accepted from the newvalue form as there are store variables; extra values are
ignored and missing values default to nil, as is usual in situations involving
multiple values.
[change_end]

[Macro]
shiftf {place}+ newvalue

Each place form may be any form acceptable as a generalized variable to setf.
In the form (shiftf place1 place2 ... placen newvalue), the values in place1
through placen are accessed and saved, and newvalue is evaluated, for a total
of n+1 values in all. Values 2 through n+1 are then stored into place1 through
placen, and value 1 (the original value of place1) is returned. It is as if all
the places form a shift register; the newvalue is shifted in from the right,
all values shift over to the left one place, and the value shifted out of
place1 is returned. For example:

(setq x (list 'a 'b 'c)) => (a b c)

(shiftf (cadr x) 'z) => b
   and now x => (a z c)

(shiftf (cadr x) (cddr x) 'q) => z
   and now x => (a (c) . q)

The effect of (shiftf place1 place2 ... placen newvalue) is equivalent to

(let ((var1 place1)
      (var2 place2)
      ...
      (varn placen))
  (setf place1 var2)
  (setf place2 var3)
  ...
  (setf placen newvalue)
  var1)

except that the latter would evaluate any subforms of each place twice, whereas
shiftf takes care to evaluate them only once. For example:

(setq n 0)
(setq x '(a b c d))
(shiftf (nth (setq n (+ n 1)) x) 'z) => b
   and now x => (a z c d)

but

(setq n 0)
(setq x '(a b c d))
(prog1 (nth (setq n (+ n 1)) x)
       (setf (nth (setq n (+ n 1)) x) 'z)) => b
   and now x => (a b z d)

Moreover, for certain place forms shiftf may be significantly more efficient
than the prog1 version.

[change_begin]
X3J13 voted in June 1989 (SETF-MULTIPLE-STORE-VARIABLES)   to extend the
specification of shiftf to allow a place whose setf method has more than one
store variable (see define-setf-method). In such a case as many values are
accepted from the newvalue form as there are store variables; extra values are
ignored and missing values default to nil, as is usual in situations involving
multiple values.
[change_end]

-------------------------------------------------------------------------------
Rationale: shiftf and rotatef have been included in Common Lisp as
generalizations of two-argument versions formerly called swapf and exchf. The
two-argument versions have been found to be very useful, but the names were
easily confused. The generalization to many argument forms and the change of
names were both inspired by the work of Suzuki [47], which indicates that use
of these primitives can make certain complex pointer-manipulation programs
clearer and easier to prove correct.
-------------------------------------------------------------------------------

[Macro]
rotatef {place}*

Each place form may be any form acceptable as a generalized variable to setf.
In the form (rotatef place1 place2 ... placen), the values in place1 through
placen are accessed and saved. Values 2 through n and value 1 are then stored
into place1 through placen. It is as if all the places form an end-around shift
register that is rotated one place to the left, with the value of place1 being
shifted around the end to placen. Note that (rotatef place1 place2) exchanges
the contents of place1 and place2.

The effect of (rotatef place1 place2 ... placen) is roughly equivalent to

(psetf place1 place2
       place2 place3
       ...
       placen place1)

except that the latter would evaluate any subforms of each place twice, whereas
rotatef takes care to evaluate them only once. Moreover, for certain place
forms rotatef may be significantly more efficient.

rotatef always returns nil.

[change_begin]
X3J13 voted in June 1989 (SETF-MULTIPLE-STORE-VARIABLES)   to extend the
specification of rotatef to allow a place whose setf method has more than one
store variable (see define-setf-method). In such a case as many values are
accepted from the newvalue form as there are store variables; extra values are
ignored and missing values default to nil, as is usual in situations involving
multiple values.
[change_end]

Other macros that manipulate generalized variables include getf, remf, incf,
decf, push, pop, assert, ctypecase, and ccase.

Macros that manipulate generalized variables must guarantee the ``obvious''
semantics: subforms of generalized-variable references are evaluated exactly as
many times as they appear in the source program, and they are evaluated in
exactly the same order as they appear in the source program.

In generalized-variable references such as shiftf, incf, push, and setf of ldb,
the generalized variables are both read and written in the same reference.
Preserving the source program order of evaluation and the number of evaluations
is particularly important.

As an example of these semantic rules, in the generalized-variable reference
(setf reference value) the value form must be evaluated after all the subforms
of the reference because the value form appears to the right of them.

The expansion of these macros must consist of code that follows these rules or
has the same effect as such code. This is accomplished by introducing temporary
variables bound to the subforms of the reference. As an optimization in the
implementation, temporary variables may be eliminated whenever it can be proved
that removing them has no effect on the semantics of the program. For example,
a constant need never be saved in a temporary variable. A variable, or for that
matter any form that does not have side effects, need not be saved in a
temporary variable if it can be proved that its value will not change within
the scope of the generalized-variable reference.

Common Lisp provides built-in facilities to take care of these semantic
complications and optimizations. Since the required semantics can be guaranteed
by these facilities, the user does not have to worry about writing correct code
for them, especially in complex cases. Even experts can become confused and
make mistakes while writing this sort of code.

[change_begin]
X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER)   to clarify the preceding
discussion about the order of evaluation of subforms in calls to setf and
related macros. The general intent is clear: evaluation proceeds from left to
right whenever possible. However, the left-to-right rule does not remove the
obligation on writers of macros and define-setf-method to work to ensure
left-to-right order of evaluation.

Let it be emphasized that, in the following discussion, a form is something
whose syntactic use is such that it will be evaluated. A subform means a form
that is nested inside another form, not merely any Lisp object nested inside a
form regardless of syntactic context.

The evaluation ordering of subforms within a generalized variable reference is
determined by the order specified by the second value returned by
get-setf-method. For all predefined generalized variable references (getf,
ldb), this order of evaluation is exactly left-to-right. When a generalized
variable reference is derived from a macro expansion, this rule is applied
after the macro is expanded to find the appropriate generalized variable
reference.

This is intended to make it clear that if the user writes a defmacro or
define-setf-method macro that doesn't preserve left-to-right evaluation order,
the order specified in the user's code holds. For example, given

(defmacro wrong-order (x y) `(getf ,y ,x))

then

(push value (wrong-order place1 place2))

will evaluate place2 first and then place1 because that is the order they are
evaluated in the macro expansion.

For the macros that manipulate generalized variables (push, pushnew, getf,
remf, incf, decf, shiftf, rotatef, psetf, setf, pop, and those defined with
define-modify-macro) the subforms of the macro call are evaluated exactly once
in left-to-right order, with the subforms of the generalized variable
references evaluated in the order specified above.

Each of push, pushnew, getf, remf, incf, decf, shiftf, rotatef, psetf, and pop
evaluates all subforms before modifying any of the generalized variable
locations. Moreover, setf itself, in the case when a call on it has more than
two arguments, performs its operation on each pair in sequence. That is, in

(setf place1 value1 place2 value2 ...)

the subforms of place1 and value1 are evaluated, the location specified by
place1 is modified to contain the value returned by value1, and then the rest
of the setf form is processed in a like manner.

For the macros check-type, ctypecase, and ccase, subforms of the generalized
variable reference are evaluated once per test of a generalized variable, but
they may be evaluated again if the type check fails (in the case of check-type)
or if none of the cases holds (in ctypecase or ccase).

For the macro assert, the order of evaluation of the generalized variable
references is not specified.
[change_end]

Another reason for building in these functions is that the appropriate
optimizations will differ from implementation to implementation. In some
implementations most of the optimization is performed by the compiler, while in
others a simpler compiler is used and most of the optimization is performed in
the macros. The cost of binding a temporary variable relative to the cost of
other Lisp operations may differ greatly between one implementation and
another, and some implementations may find it best never to remove temporary
variables except in the simplest cases.

A good example of the issues involved can be seen in the following
generalized-variable reference:

(incf (ldb byte-field variable))

This ought to expand into something like

(setq variable
      (dpb (1+ (ldb byte-field variable))
           byte-field
           variable))

In this expansion example we have ignored the further complexity of returning
the correct value, which is the incremented byte, not the new value of
variable. Note that the variable byte-field is evaluated twice, and the
variable variable is referred to three times: once as the location in which to
store a value, and twice during the computation of that value.

Now consider this expression:

(incf (ldb (aref byte-fields (incf i))
           (aref (determine-words-array) i)))

It ought to expand into something like this:

(let ((temp1 (aref byte-fields (incf i)))
      (temp2 (determine-words-array)))
  (setf (aref temp2 i)
        (dpb (1+ (ldb temp1 (aref temp2 i)))
             temp1
             (aref temp2 i))))

Again we have ignored the complexity of returning the correct value. What is
important here is that the expressions (incf i) and (determine-words-array)
must not be duplicated because each may have a side effect or be affected by
side effects.

[change_begin]
X3J13 voted in January 1989 (SETF-SUB-METHODS)   to specify more precisely the
order of evaluation of subforms when setf is used with an access function that
itself takes a place as an argument, for example, ldb, mask-field, and getf.
(The vote also discussed the function char-bit, but another vote
(CHARACTER-PROPOSAL)   removed that function from the language.) The setf
methods for such accessors produce expansions that effectively require explicit
calls to get-setf-method.

The code produced as the macro expansion of a setf form that itself admits a
generalized variable as an argument must essentially do the following major
steps:

   *  It evaluates the value-producing subforms, in left-to-right order, and
     binds the temporary variables to them; this is called binding the
     temporaries.

   *  It reads the value from the generalized variable, using the supplied
     accessing form, to get the old value; this is called doing the access.
     Note that this is done after all the evaluations of the preceding step,
     including any side effects they may have.

   *  It binds the store variable to a new value, and then installs this new
     value into the generalized variable using the supplied storing form; this
     is called doing the store.

Doing the access for a generalized variable reference is not part of the series
of evaluations that must be done in left-to-right order.

The place-specifier forms ldb, mask-field, and getf admit (other) place
specifiers as arguments. During the setf expansion of these forms, it is
necessary to call get-setf-method to determine how the inner, nested
generalized variable must be treated.

In a form such as

(setf (ldb byte-spec place-form) newvalue-form)

the place referred to by the place-form must always be both accessed and
updated; note that the update is to the generalized variable specified by
place-form, not to any object of type integer.

Thus this call to setf should generate code to do the following:

   *  Evaluate byte-spec and bind into a temporary
   *  Bind the temporaries for place-form
   *  Evaluate newvalue-form and bind into the store variable
   *  Do the access to place-form
   *  Do the store into place-form with the given bit-field of the accessed
     integer replaced with the value in the store variable

If the evaluation of newvalue-form alters what is found in the given place-such
as setting a different bit-field of the integer-then the change of the
bit-field denoted by byte-spec will be to that altered integer, because the
access step must be done after the newvalue-form evaluation. Nevertheless, the
evaluations required for binding the temporaries are done before the evaluation
of the newvalue-form, thereby preserving the required left-to-right evaluation
order.

The treatment of mask-field is similar to that of ldb.

In a form such as:

(setf (getf place-form ind-form) newvalue-form)

the place referred to by the place-form must always be both accessed and
updated; note that the update is to the generalized variable specified by
place-form, not necessarily to the particular list which is the property list
in question.

Thus this call to setf should generate code to do the following:

   *  Bind the temporaries for place-form
   *  Evaluate ind-form and bind into a temporary
   *  Evaluate the newvalue-form and bind into the store variable
   *  Do the access to place-form
   *  Do the store into place-form with a possibly new property list obtained
     by combining the results of the evaluations and the access

If the evaluation of newvalue-form alters what is found in the given place-such
as setting a different named property in the list-then the change of the
property denoted by ind-form will be to that altered list, because the access
step is done after the newvalue-form evaluation. Nevertheless, the evaluations
required for binding the temporaries are done before the evaluation of the
newvalue-form, thereby preserving the required left-to-right evaluation order.

Note that the phrase ``possibly new property list'' treats the implementation
of property lists as a ``black box''; it can mean that the former property list
is somehow destructively re-used, or it can mean partial or full copying of it.
A side effect may or may not occur; therefore setf must proceed as if the
resultant property list were a different copy needing to be stored back into
the generalized variable.
[change_end]

The Common Lisp facilities provided to deal with these semantic issues include:

   *  Built-in macros such as setf and push that follow the semantic rules.

   *  The define-modify-macro macro, which allows new generalized-variable
     manipulating macros (of a certain restricted kind) to be defined easily.
     It takes care of the semantic rules automatically.

   *  The defsetf macro, which allows new types of generalized-variable
     references to be defined easily. It takes care of the semantic rules
     automatically.

   *  The define-setf-method macro and the get-setf-method function, which
     provide access to the internal mechanisms when it is necessary to define a
     complicated new type of generalized-variable reference or
     generalized-variable-manipulating macro.

[change_begin]
Also important are the changes that allow lexical environments to be used in
appropriate ways in setf methods.
[change_end]

[Macro]
define-modify-macro name lambda-list function
[doc-string]

This macro defines a read-modify-write macro named name. An example of such a
macro is incf. The first subform of the macro will be a generalized-variable
reference. The function is literally the function to apply to the old contents
of the generalized-variable to get the new contents; it is not evaluated.
lambda-list describes the remaining arguments for the function; these arguments
come from the remaining subforms of the macro after the generalized-variable
reference. lambda-list may contain &optional and &rest markers. (The &key
marker is not permitted here; &rest suffices for the purposes of
define-modify-macro.) doc-string is documentation for the macro name being
defined.

The expansion of a define-modify-macro is equivalent to the following, except
that it generates code that follows the semantic rules outlined above.

(defmacro name (reference . lambda-list)
  doc-string
  `(setf ,reference
         (function ,reference ,arg1 ,arg2 ...)))

where arg1, arg2, ..., are the parameters appearing in lambda-list; appropriate
provision is made for a &rest parameter.

As an example, incf could have been defined by:

(define-modify-macro incf (&optional (delta 1)) +)

An example of a possibly useful macro not predefined in Common Lisp is

(define-modify-macro unionf (other-set &rest keywords) union)

[change_begin]
X3J13 voted in March 1988 (GET-SETF-METHOD-ENVIRONMENT)   to specify that
define-modify-macro creates macros that take &environment arguments and perform
the equivalent of correctly passing such lexical environments to
get-setf-method in order to correctly maintain lexical references.
[change_end]

[Macro]

defsetf access-fn {update-fn [doc-string] |

                   lambda-list (store-variable)

                   [[{declaration}* | doc-string]] {form}*}

This defines how to setf a generalized-variable reference of the form
(access-fn ...). The value of a generalized-variable reference can always be
obtained simply by evaluating it, so access-fn should be the name of a function
or a macro.

The user of defsetf provides a description of how to store into the
generalized-variable reference and return the value that was stored (because
setf is defined to return this value). The implementation of defsetf takes care
of ensuring that subforms of the reference are evaluated exactly once and in
the proper left-to-right order. In order to do this, defsetf requires that
access-fn be a function or a macro that evaluates its arguments, behaving like
a function. Furthermore, a setf of a call on access-fn will also evaluate all
of access-fn's arguments; it cannot treat any of them specially. This means
that defsetf cannot be used to describe how to store into a generalized
variable that is a byte, such as (ldb field reference). To handle situations
that do not fit the restrictions imposed by defsetf, use define-setf-method,
which gives the user additional control at the cost of increased complexity.

A defsetf declaration may take one of two forms. The simple form is

(defsetf access-fn update-fn doc-string)

The update-fn must name a function (or macro) that takes one more argument than
access-fn takes. When setf is given a place that is a call on access-fn, it
expands into a call on update-fn that is given all the arguments to access-fn
and also, as its last argument, the new value (which must be returned by
update-fn as its value). For example, the effect of

(defsetf symbol-value set)

is built into the Common Lisp system. This causes the expansion

(setf (symbol-value foo) fu) -> (set foo fu)

for example. Note that

(defsetf car rplaca)

would be incorrect because rplaca does not return its last argument.

The complex form of defsetf looks like

(defsetf access-fn lambda-list (store-variable) . body)

and resembles defmacro. The body must compute the expansion of a setf of a call
on access-fn.

The lambda-list describes the arguments of access-fn. &optional, &rest, and
&key markers are permitted in lambda-list. Optional arguments may have defaults
and ``supplied-p'' flags. The store-variable describes the value to be stored
into the generalized-variable reference.

-------------------------------------------------------------------------------
Rationale: The store-variable is enclosed in parentheses to provide for an
extension to multiple store variables that would receive multiple values from
the second subform of setf. The rules given below for coding setf methods
discuss the proper handling of multiple store variables to allow for the
possibility that this extension may be incorporated into Common Lisp in the
future.
-------------------------------------------------------------------------------

The body forms can be written as if the variables in the lambda-list were bound
to subforms of the call on access-fn and the store-variable were bound to the
second subform of setf. However, this is not actually the case. During the
evaluation of the body forms, these variables are bound to names of temporary
variables, generated as if by gensym or gentemp, that will be bound by the
expansion of setf to the values of those subforms. This binding permits the
body forms to be written without regard for order-of-evaluation issues. defsetf
arranges for the temporary variables to be optimized out of the final result in
cases where that is possible. In other words, an attempt is made by defsetf to
generate the best code possible in a particular implementation.

Note that the code generated by the body forms must include provision for
returning the correct value (the value of store-variable). This is handled by
the body forms rather than by defsetf because in many cases this value can be
returned at no extra cost, by calling a function that simultaneously stores
into the generalized variable and returns the correct value.

An example of the use of the complex form of defsetf:

(defsetf subseq (sequence start &optional end) (new-sequence)
  `(progn (replace ,sequence ,new-sequence
                   :start1 ,start :end1 ,end)
          ,new-sequence))

[change_begin]
X3J13 voted in March 1988 (FLET-IMPLICIT-BLOCK)   to specify that the body of
the expander function defined by the complex form of defsetf is implicitly
enclosed in a block construct whose name is the same as the name of the
access-fn. Therefore return-from may be used to exit from the function.

X3J13 voted in March 1989 (DEFINING-MACROS-NON-TOP-LEVEL)   to clarify that,
while defining forms normally appear at top level, it is meaningful to place
them in non-top-level contexts; the complex form of defsetf must define the
expander function within the enclosing lexical environment, not within the
global environment.
[change_end]

The underlying theory by which setf and related macros arrange to conform to
the semantic rules given above is that from any generalized-variable reference
one may derive its ``setf method,'' which describes how to store into that
reference and which subforms of it are evaluated.

-------------------------------------------------------------------------------
Compatibility note: To avoid confusion, it should be noted that the use of the
word ``method'' here in connection with setf has nothing to do with its use in
Lisp Machine Lisp in connection with message-passing and the Lisp Machine Lisp
``flavor system.''
[change_begin]
And of course it also has nothing to do with the methods in the Common Lisp
Object System (CLOS)   .
[change_end]
-------------------------------------------------------------------------------

Given knowledge of the subforms of the reference, it is possible to avoid
evaluating them multiple times or in the wrong order. A setf method for a given
access form can be expressed as five values:

   *  A list of temporary variables

   *  A list of value forms (subforms of the given form) to whose values the
     temporary variables are to be bound

   *  A second list of temporary variables, called store variables

   *  A storing form

   *  An accessing form

The temporary variables will be bound to the values of the value forms as if by
let*; that is, the value forms will be evaluated in the order given and may
refer to the values of earlier value forms by using the corresponding
variables.

The store variables are to be bound to the values of the newvalue form, that
is, the values to be stored into the generalized variable. In almost all cases
only a single value is to be stored, and there is only one store variable.

The storing form and the accessing form may contain references to the temporary
variables (and also, in the case of the storing form, to the store variables).
The accessing form returns the value of the generalized variable. The storing
form modifies the value of the generalized variable and guarantees to return
the values of the store variables as its values; these are the correct values
for setf to return. (Again, in most cases there is a single store variable and
thus a single value to be returned.) The value returned by the accessing form
is, of course, affected by execution of the storing form, but either of these
forms may be evaluated any number of times and therefore should be free of side
effects (other than the storing action of the storing form).

The temporary variables and the store variables are generated names, as if by
gensym or gentemp, so that there is never any problem of name clashes among
them, or between them and other variables in the program. This is necessary to
make the special forms that do more than one setf in parallel work properly;
these are psetf, shiftf, and rotatef. Computation of the setf method must
always create new variable names; it may not return the same ones every time.

Some examples of setf methods for particular forms:

   *  For a variable x:

     ()
     ()
     (g0001)
     (setq x g0001)
     x

   *  For (car exp):

     (g0002)
     (exp)
     (g0003)
     (progn (rplaca g0002 g0003) g0003)
     (car g0002)

   *  For (subseq seq s e):

     (g0004 g0005 g0006)
     (seq s e)
     (g0007)
     (progn (replace g0004 g0007 :start1 g0005 :end1 g0006)
            g0007)
     (subseq g0004 g0005 g0006)

[Macro]

define-setf-method access-fn lambda-list
                   [[ {declaration}* | doc-string ]]  {form}*

This defines how to setf a generalized-variable reference that is of the form
(access-fn...). The value of a generalized-variable reference can always be
obtained simply by evaluating it, so access-fn should be the name of a function
or a macro.

The lambda-list describes the subforms of the generalized-variable reference,
as with defmacro. The result of evaluating the forms in the body must be five
values representing the setf method, as described above. Note that
define-setf-method differs from the complex form of defsetf in that while the
body is being executed the variables in lambda-list are bound to parts of the
generalized-variable reference, not to temporary variables that will be bound
to the values of such parts. In addition, define-setf-method does not have
defsetf's restriction that access-fn must be a function or a function-like
macro; an arbitrary defmacro destructuring pattern is permitted in lambda-list.

By definition there are no good small examples of define-setf-method because
the easy cases can all be handled by defsetf. A typical use is to define the
setf method for ldb:

;;; SETF method for the form (LDB bytespec int).
;;; Recall that the int form must itself be suitable for SETF.
(define-setf-method ldb (bytespec int)
  (multiple-value-bind (temps vals stores
                        store-form access-form)
      (get-setf-method int)         ;Get SETF method for int
    (let ((btemp (gensym))          ;Temp var for byte specifier
          (store (gensym))          ;Temp var for byte to store
          (stemp (first stores)))   ;Temp var for int to store
      ;; Return the SETF method for LDB as five values.
      (values (cons btemp temps)    ;Temporary variables
              (cons bytespec vals)  ;Value forms
              (list store)          ;Store variables
              `(let ((,stemp (dpb ,store ,btemp ,access-form)))
                 ,store-form
                 ,store)                     ;Storing form
              `(ldb ,btemp ,access-form)     ;Accessing form
              ))))

[change_begin]
X3J13 voted in March 1988 (GET-SETF-METHOD-ENVIRONMENT)   to specify that the
&environment lambda-list keyword may appear in the lambda-list in the same
manner as for defmacro in order to obtain the lexical environment of the call
to the setf macro. The preceding example should be modified to take advantage
of this new feature. The setf method must accept an &environment parameter,
which will receive the lexical environment of the call to setf; this
environment must then be given to get-setf-method in order that it may
correctly use any locally bound setf method that might be applicable to the
place form that appears as the second argument to ldb in the call to setf.

;;; SETF method for the form (LDB bytespec int).
;;; Recall that the int form must itself be suitable for SETF.
;;; Note the use of an &environment parameter to receive the
;;; lexical environment of the call for use with GET-SETF-METHOD.
(define-setf-method ldb (bytespec int &environment env)
  (multiple-value-bind (temps vals stores
                        store-form access-form)
      (get-setf-method int env)     ;Get SETF method for int
    (let ((btemp (gensym))          ;Temp var for byte specifier
          (store (gensym))          ;Temp var for byte to store
          (stemp (first stores)))   ;Temp var for int to store
      ;; Return the SETF method for LDB as five values.
      (values (cons btemp temps)    ;Temporary variables
              (cons bytespec vals)  ;Value forms
              (list store)          ;Store variables
              `(let ((,stemp (dpb ,store ,btemp ,access-form)))
                 ,store-form
                 ,store)                     ;Storing form
              `(ldb ,btemp ,access-form)     ;Accessing form
              ))))

X3J13 voted in March 1988 (FLET-IMPLICIT-BLOCK)   to specify that the body of
the expander function defined by define-setf-method is implicitly enclosed in a
block construct whose name is the same as the name of the access-fn. Therefore
return-from may be used to exit from the function.

X3J13 voted in March 1989 (DEFINING-MACROS-NON-TOP-LEVEL)   to clarify that,
while defining forms normally appear at top level, it is meaningful to place
them in non-top-level contexts; define-setf-method must define the expander
function within the enclosing lexical environment, not within the global
environment.
[change_end]

[old_change_begin]

[Function]
get-setf-method form

get-setf-method returns five values constituting the setf method for form. The
form must be a generalized-variable reference. get-setf-method takes care of
error-checking and macro expansion and guarantees to return exactly one store
variable.

As an example, an extremely simplified version of setf, allowing no more and no
fewer than two subforms, containing no optimization to remove unnecessary
variables, and not allowing storing of multiple values, could be defined by:

(defmacro setf (reference value)
  (multiple-value-bind (vars vals stores store-form access-form)
      (get-setf-method reference)
    (declare (ignore access-form))
    `(let* ,(mapcar #'list
                    (append vars stores)
                    (append vals (list value)))
       ,store-form)))

[old_change_end]

[change_begin]
X3J13 voted in March 1988 (GET-SETF-METHOD-ENVIRONMENT)   to add an optional
environment argument to get-setf-method. The revised definition and example are
as follows.

[Function]
get-setf-method form &optional env

get-setf-method returns five values constituting the setf method for form. The
form must be a generalized-variable reference. The env must be an environment
of the sort obtained through the &environment lambda-list keyword; if env is
nil or omitted, the null lexical environment is assumed. get-setf-method takes
care of error checking and macro expansion and guarantees to return exactly one
store variable.

As an example, an extremely simplified version of setf, allowing no more and no
fewer than two subforms, containing no optimization to remove unnecessary
variables, and not allowing storing of multiple values, could be defined by:

(defmacro setf (reference value &environment env)
  (multiple-value-bind (vars vals stores store-form access-form)
      (get-setf-method reference env)     ;Note use of environment
    (declare (ignore access-form))
    `(let* ,(mapcar #'list
                    (append vars stores)
                    (append vals (list value)))
       ,store-form)))

[change_end]

[old_change_begin]

[Function]
get-setf-method-multiple-value form

get-setf-method-multiple-value returns five values constituting the setf method
for form. The form must be a generalized-variable reference. This is the same
as get-setf-method except that it does not check the number of store variables;
use this in cases that allow storing multiple values into a generalized
variable. There are no such cases in standard Common Lisp, but this function is
provided to allow for possible extensions.
[old_change_end]

[change_begin]
X3J13 voted in March 1988 (GET-SETF-METHOD-ENVIRONMENT)   to add an optional
environment argument to get-setf-method. The revised definition is as follows.

[Function]
get-setf-method-multiple-value form &optional env

get-setf-method-multiple-value returns five values constituting the setf method
for form. The form must be a generalized-variable reference. The env must be an
environment of the sort obtained through the &environment lambda-list keyword;
if env is nil or omitted, the null lexical environment is assumed.

This is the same as get-setf-method except that it does not check the number of
store variables; use this in cases that allow storing multiple values into a
generalized variable. There are no such cases in standard Common Lisp, but this
function is provided to allow for possible extensions.

X3J13 voted in March 1988 (GET-SETF-METHOD-ENVIRONMENT)   to clarify that a
setf method for a functional name is applicable only when the global binding of
that name is lexically visible. If such a name has a local binding introduced
by flet, labels, or macrolet, then global definitions of setf methods for that
name do not apply and are not visible. All of the standard Common Lisp macros
that modify a setf place (for example, incf, decf, pop, and rotatef) obey this
convention.
[change_end]

-------------------------------------------------------------------------------

7.3. Function Invocation

The most primitive form for function invocation in Lisp of course has no name;
any list that has no other interpretation as a macro call or special form is
taken to be a function call. Other constructs are provided for less common but
nevertheless frequently useful situations.

[Function]
apply function arg &rest more-args

This applies function to a list of arguments.

[old_change_begin]
The function may be a compiled-code object, or a lambda-expression, or a
symbol; in the latter case the global functional value of that symbol is used
(but it is illegal for the symbol to be the name of a macro or special form).
[old_change_end]

[change_begin]
X3J13 voted in June 1988 (FUNCTION-TYPE)   to allow the function to be only of
type symbol or function; a lambda-expression is no longer acceptable as a
functional argument. One must use the function special form or the abbreviation
#' before a lambda-expression that appears as an explicit argument form.
[change_end]

The arguments for the function consist of the last argument to apply appended
to the end of a list of all the other arguments to apply but the function
itself; it is as if all the arguments to apply except the function were given
to list* to create the argument list. For example:

(setq f '+) (apply f '(1 2)) => 3
(setq f #'-) (apply f '(1 2)) => -1
(apply #'max 3 5 '(2 7 3)) => 7
(apply 'cons '((+ 2 3) 4)) =>
        ((+ 2 3) . 4) not (5 . 4)
(apply #'+ '()) => 0

Note that if the function takes keyword arguments, the keywords as well as the
corresponding values must appear in the argument list:

(apply #'(lambda (&key a b) (list a b)) '(:b 3)) => (nil 3)

This can be very useful in conjunction with the &allow-other-keys feature:

(defun foo (size &rest keys &key double &allow-other-keys)
  (let ((v (apply #'make-array size :allow-other-keys t keys)))
    (if double (concatenate (type-of v) v v) v)))

(foo 4 :initial-contents '(a b c d) :double t)
   => #(a b c d a b c d)

[Function]
funcall fn &rest arguments

(funcall fn a1 a2 ... an) applies the function fn to the arguments a1, a2, ...,
an. The fn may not be a special form or a macro; this would not be meaningful.

[change_begin]
X3J13 voted in June 1988 (FUNCTION-TYPE)   to allow the fn to be only of type
symbol or function; a lambda-expression is no longer acceptable as a functional
argument. One must use the function special form or the abbreviation #' before
a lambda-expression that appears as an explicit argument form.
[change_end]

For example:

(cons 1 2) => (1 . 2)
(setq cons (symbol-function '+))
(funcall cons 1 2) => 3

The difference between funcall and an ordinary function call is that the
function is obtained by ordinary Lisp evaluation rather than by the special
interpretation of the function position that normally occurs.

-------------------------------------------------------------------------------
Compatibility note: The Common Lisp function funcall corresponds roughly to the
Interlisp primitive apply*.
-------------------------------------------------------------------------------

[Constant]
call-arguments-limit

The value of call-arguments-limit is a positive integer that is the upper
exclusive bound on the number of arguments that may be passed to a function.
This bound depends on the implementation but will not be smaller than 50.
(Implementors are encouraged to make this limit as large as practicable without
sacrificing performance.) The value of call-arguments-limit must be at least as
great as that of lambda-parameters-limit. See also multiple-values-limit.

-------------------------------------------------------------------------------

7.4. Simple Sequencing

Each of the constructs in this section simply evaluates all the argument forms
in order. They differ only in what results are returned.

[Special Form]
progn {form}*

The progn construct takes a number of forms and evaluates them sequentially, in
order, from left to right. The values of all the forms but the last are
discarded; whatever the last form returns is returned by the progn form. One
says that all the forms but the last are evaluated for effect, because their
execution is useful only for the side effects caused, but the last form is
executed for value.

progn is the primitive control structure construct for ``compound statements,''
such as begin-end blocks in Algol-like languages. Many Lisp constructs are
``implicit progn'' forms: as part of their syntax each allows many forms to be
written that are to be evaluated sequentially, discarding the results of all
forms but the last and returning the results of the last form.

If the last form of the progn returns multiple values, then those multiple
values are returned by the progn form. If there are no forms for the progn,
then the result is nil. These rules generally hold for implicit progn forms as
well.

[Macro]
prog1 first {form}*

prog1 is similar to progn, but it returns the value of its first form. All the
argument forms are executed sequentially; the value of the first form is saved
while all the others are executed and is then returned.

prog1 is most commonly used to evaluate an expression with side effects and to
return a value that must be computed before the side effects happen. For
example:

(prog1 (car x) (rplaca x 'foo))

alters the car of x to be foo and returns the old car of x.

prog1 always returns a single value, even if the first form tries to return
multiple values. As a consequence, (prog1 x) and (progn x) may behave
differently if x can produce multiple values. See multiple-value-prog1. A point
of style: although prog1 can be used to force exactly a single value to be
returned, it is conventional to use the function values for this purpose.

[Macro]
prog2 first second {form}*

prog2 is similar to prog1, but it returns the value of its second form. All the
argument forms are executed sequentially; the value of the second form is saved
while all the other forms are executed and is then returned. prog2 is provided
mostly for historical compatibility.

(prog2 a b c ... z) == (progn a (prog1 b c ... z))

Occasionally it is desirable to perform one side effect, then a value-producing
operation, then another side effect. In such a peculiar case, prog2 is fairly
perspicuous. For example:

(prog2 (open-a-file) (process-the-file) (close-the-file))
                     ;value is that of process-the-file

prog2, like prog1, always returns a single value, even if the second form tries
to return multiple values. As a consequence of this, (prog2 x y) and (progn x
y) may behave differently if y can produce multiple values.

-------------------------------------------------------------------------------

7.5. Establishing New Variable Bindings

During the invocation of a function represented by a lambda-expression (or a
closure of a lambda-expression, as produced by function), new bindings are
established for the variables that are the parameters of the lambda-expression.
These bindings initially have values determined by the parameter-binding
protocol discussed in section 5.2.2.

The following constructs may also be used to establish bindings of variables,
both ordinary and functional.

[Special Form]
let ({var | (var value)}*) {declaration}* {form}*

A let form can be used to execute a series of forms with specified variables
bound to specified values.

More precisely, the form

(let ((var1 value1)
      (var2 value2)
      ...
      (varm valuem))
  declaration1
  declaration2
  ...
  declarationp
  body1
  body2
  ...
  bodyn)

first evaluates the expressions value1, value2, and so on, in that order,
saving the resulting values. Then all of the variables varj are bound to the
corresponding values in parallel; each binding will be a lexical binding unless
there is a special declaration to the contrary. The expressions bodyk are then
evaluated in order; the values of all but the last are discarded (that is, the
body of a let form is an implicit progn). The let form returns what evaluating
bodyn produces (if the body is empty, which is fairly useless, let returns nil
as its value). The bindings of the variables have lexical scope and indefinite
extent.

Instead of a list (varj valuej), one may write simply varj. In this case varj
is initialized to nil. As a matter of style, it is recommended that varj be
written only when that variable will be stored into (such as by setq) before
its first use. If it is important that the initial value be nil rather than
some undefined value, then it is clearer to write out (varj nil) if the initial
value is intended to mean ``false,'' or (varj '()) if the initial value is
intended to be an empty list. Note that the code

(let (x)
  (declare (integer x))
  (setq x (gcd y z))
  ...)

is incorrect; although x is indeed set before it is used, and is set to a value
of the declared type integer, nevertheless x momentarily takes on the value nil
in violation of the type declaration.

Declarations may appear at the beginning of the body of a let. See declare.

[change_begin]
See also destructuring-bind.

X3J13 voted in January 1989 (VARIABLE-LIST-ASYMMETRY)   to regularize the
binding formats for do, do*, let, let*, prog, prog*, and compiler-let. The new
syntactic definition for let makes the value optional:

[Special Form]
let ({var | (var [value])}*) {declaration}* {form}*

This changes let to allow a list (var) to appear, meaning the same as simply
var.
[change_end]

[Special Form]
let* ({var | (var value)}*) {declaration}* {form}*

let* is similar to let, but the bindings of variables are performed
sequentially rather than in parallel. This allows the expression for the value
of a variable to refer to variables previously bound in the let* form.

More precisely, the form

(let* ((var1 value1)
       (var2 value2)
       ...
       (varm valuem))
  declaration1
  declaration2
  ...
  declarationp
  body1
  body2
  ...
  bodyn)

first evaluates the expression value1, then binds the variable var1 to that
value; then it evaluates value2 and binds var2; and so on. The expressions
bodyj are then evaluated in order; the values of all but the last are discarded
(that is, the body of a let* form is an implicit progn). The let* form returns
the results of evaluating bodyn (if the body is empty, which is fairly useless,
let* returns nil as its value). The bindings of the variables have lexical
scope and indefinite extent.

Instead of a list (varj valuej), one may write simply varj. In this case varj
is initialized to nil. As a matter of style, it is recommended that varj be
written only when that variable will be stored into (such as by setq) before
its first use. If it is important that the initial value be nil rather than
some undefined value, then it is clearer to write out (varj nil) if the initial
value is intended to mean ``false,'' or (varj '()) if the initial value is
intended to be an empty list.

Declarations may appear at the beginning of the body of a let*. See declare.

[change_begin]
X3J13 voted in January 1989 (VARIABLE-LIST-ASYMMETRY)   to regularize the
binding formats for do, do*, let, let*, prog, prog*, and compiler-let. The new
syntactic definition for let* makes the value optional:

[Special Form]
let* ({var | (var [value])}*) {declaration}* {form}*

This changes let* to allow a list (var) to appear, meaning the same as simply
var.
[change_end]

[old_change_begin]

[Special Form]
compiler-let ({var | (var value)}*) {form}*

When executed by the Lisp interpreter, compiler-let behaves exactly like let
with all the variable bindings implicitly declared special. When the compiler
processes this form, however, no code is compiled for the bindings; instead,
the processing of the body by the compiler (including, in particular, the
expansion of any macro calls within the body) is done with the special
variables bound to the indicated values in the execution context of the
compiler. This is primarily useful for communication among complicated macros.

Declarations may not appear at the beginning of the body of a compiler-let.

-------------------------------------------------------------------------------
Rationale: Because of the unorthodox handling by compiler-let of its variable
bindings, it would be complicated and confusing to permit declarations that
apparently referred to the variables bound by compiler-let. Disallowing
declarations eliminates the problem.
-------------------------------------------------------------------------------

X3J13 voted in January 1989 (VARIABLE-LIST-ASYMMETRY)   to regularize the
binding formats for do, do*, let, let*, prog, prog*, and compiler-let. The new
syntactic definition for compiler-let makes the value optional:

[Macro]
compiler-let ({var | (var [value])}*) {form}*

This changes compiler-let to allow a list (var) to appear, meaning the same as
simply var.
[old_change_end]

[change_begin]
X3J13 voted in June 1989 (COMPILER-LET-CONFUSION)   to remove compiler-let from
the language. Many uses of compiler-let can be replaced with more portable code
that uses macrolet or symbol-macrolet.
[change_end]

[Special Form]
progv symbols values {form}*

progv is a special form that allows binding one or more dynamic variables whose
names may be determined at run time. The sequence of forms (an implicit progn)
is evaluated with the dynamic variables whose names are in the list symbols
bound to corresponding values from the list values. (If too few values are
supplied, the remaining symbols are bound and then made to have no value; see
makunbound. If too many values are supplied, the excess values are ignored.)
The results of the progv form are those of the last form. The bindings of the
dynamic variables are undone on exit from the progv form. The lists of symbols
and values are computed quantities; this is what makes progv different from,
for example, let, where the variable names are stated explicitly in the program
text.

progv is particularly useful for writing interpreters for languages embedded in
Lisp; it provides a handle on the mechanism for binding dynamic variables.

[Special Form]

flet ({(name lambda-list
         [[ {declaration}* | doc-string ]] {form}*)}*)
     {form}*
labels ({(name lambda-list
         [[ {declaration}* | doc-string ]] {form}*)}*)
     {form}*
macrolet ({(name varlist
         [[ {declaration}* | doc-string ]] {form}*)}*)
     {form}*

flet may be used to define locally named functions. Within the body of the flet
form, function names matching those defined by the flet refer to the locally
defined functions rather than to the global function definitions of the same
name.

Any number of functions may be simultaneously defined. Each definition is
similar in format to a defun form: first a name, then a parameter list (which
may contain &optional, &rest, or &key parameters), then optional declarations
and documentation string, and finally a body.

(flet ((safesqrt (x) (sqrt (abs x))))
  ;; The safesqrt function is used in two places.
  (safesqrt (apply #'+ (map 'list #'safesqrt longlist))))

The labels construct is identical in form to the flet construct. These
constructs differ in that the scope of the defined function names for flet
encompasses only the body, whereas for labels it encompasses the function
definitions themselves. That is, labels can be used to define mutually
recursive functions, but flet cannot. This distinction is useful. Using flet
one can locally redefine a global function name, and the new definition can
refer to the global definition; the same construction using labels would not
have that effect.

(defun integer-power (n k)       ;A highly "bummed" integer
  (declare (integer n))          ; exponentiation routine
  (declare (type (integer 0 *) k))
  (labels ((expt0 (x k a)
             (declare (integer x a) (type (integer 0 *) k))
             (cond ((zerop k) a)
                   ((evenp k) (expt1 (* x x) (floor k 2) a))
                   (t (expt0 (* x x) (floor k 2) (* x a)))))
           (expt1 (x k a)
             (declare (integer x a) (type (integer 1 *) k))
             (cond ((evenp k) (expt1 (* x x) (floor k 2) a))
                   (t (expt0 (* x x) (floor k 2) (* x a))))))
    (expt0 n k 1)))

macrolet is similar in form to flet but defines local macros, using the same
format used by defmacro. The names established by macrolet as names for macros
are lexically scoped.

[change_begin]
I have observed that, while most Common Lisp users pronounce macrolet to rhyme
with ``silhouette,'' a small but vocal minority pronounce it to rhyme with
``Chevrolet.'' A very few extremists furthermore adjust their pronunciation of
flet similarly: they say ``flay.'' Hey, hey! Tr鑚 outré.
[change_end]

Macros often must be expanded at ``compile time'' (more generally, at a time
before the program itself is executed), and so the run-time values of variables
are not available to macros defined by macrolet.

[old_change_begin]
The precise rule is that the macro-expansion functions defined by macrolet are
defined in the global environment; lexically scoped entities that would
ordinarily be lexically apparent are not visible within the expansion
functions.
[old_change_end]

[change_begin]
X3J13 voted in March 1989 (DEFINING-MACROS-NON-TOP-LEVEL)   to retract the
previous sentence and specify that the macro-expansion functions created by
macrolet are defined in the lexical environment in which the macrolet form
appears, not in the null lexical environment. Declarations, macrolet
definitions, and symbol-macrolet definitions affect code within the expansion
functions in a macrolet, but the consequences are undefined if such code
attempts to refer to any local variable or function bindings that are visible
in that lexical environment.
[change_end]

However, lexically scoped entities are visible within the body of the macrolet
form and are visible to the code that is the expansion of a macro call. The
following example should make this clear:

;;; Example of scoping in macrolet.

(defun foo (x flag)
  (macrolet ((fudge (z)
                ;;The parameters x and flag are not accessible
                ;; at this point; a reference to flag would be to
                ;; the global variable of that name.
                `(if flag
                     (* ,z ,z)
                     ,z)))
    ;;The parameters x and flag are accessible here.
    (+ x
       (fudge x)
       (fudge (+ x 1)))))

The body of the macrolet becomes

(+ x
   (if flag
       (* x x)
       x))
   (if flag
       (* (+ x 1) (+ x 1))
       (+ x 1)))

after macro expansion. The occurrences of x and flag legitimately refer to the
parameters of the function foo because those parameters are visible at the site
of the macro call which produced the expansion.

[change_begin]
X3J13 voted in March 1988 (FLET-IMPLICIT-BLOCK)   to specify that the body of
each function or expander function defined by flet, labels, or macrolet is
implicitly enclosed in a block construct whose name is the same as the name of
the function. Therefore return-from may be used to exit from the function.

X3J13 voted in March 1989 (FUNCTION-NAME)   to extend flet and labels to accept
any function-name (a symbol or a list whose car is setf-see section 7.1) as a
name for a function to be locally defined. In this way one can create local
definitions for setf expansion functions. (X3J13 explicitly declined to extend
macrolet in the same manner.)

X3J13 voted in March 1988 (FLET-DECLARATIONS)   to change flet, labels, and
macrolet to allow declarations to appear before the body. The new descriptions
are therefore as follows:

[Special Form]

flet ({(name lambda-list
         [[ {declaration}* | doc-string ]] {form}*)}*)
     {declaration}* {form}*
labels ({(name lambda-list
         [[ {declaration}* | doc-string ]] {form}*)}*)
     {declaration}* {form}*
macrolet ({(name varlist
         [[ {declaration}* | doc-string ]] {form}*)}*)
     {declaration}* {form}*

These are now syntactically more similar to such other binding forms as let.

For flet and labels, the bodies of the locally defined functions are part of
the scope of pervasive declarations appearing before the main body. (This is
consistent with the treatment of initialization forms in let.) For macrolet,
however, the bodies of the locally defined macro expander functions are not
included in the scope of pervasive declarations appearing before the main body.
(This is consistent with the rule, stated below, that the bodies of macro
expander functions are in the global environment, not the local lexical
environment.) Here is an example:

(flet ((stretch (x) (* x *stretch-factor*))
       (chop (x) (- x *chop-margin*)))
  (declare (inline stretch chop))   ;Illegal in original Common Lisp
  (if (> x *chop-margin*) (stretch (chop x)) (chop (stretch x))))

X3J13 voted to permit declarations of the sort noted above.
[change_end]

[change_begin]

[Special Form]

symbol-macrolet ({(var expansion)}*)
                  {declaration}* {form}*

X3J13 voted in June 1988 (CLOS) to adopt the Common Lisp Object System. Part of
this proposal is a general mechanism, symbol-macrolet, for treating certain
variable names as if they were parameterless macro calls. This facility may be
useful independent of CLOS. X3J13 voted in March 1989
(SYMBOL-MACROLET-SEMANTICS)   to modify the definition of symbol-macrolet
substantially and also voted (SYMBOL-MACROLET-DECLARE)   to allow declarations
before the body of symbol-macrolet but with peculiar treatment of special and
type declarations.

The forms are executed as an implicit progn in a lexical environment that
causes every reference to any defined var to be replaced by the corresponding
expansion. It is as if the reference to the var were a parameterless macro
call; the expansion is evaluated or otherwise processed in place of the
reference (in particular, the expansion form is itself subject to further
expansion-this is one of the changes (SYMBOL-MACROLET-SEMANTICS)   from the
original definition in the CLOS proposal). Note, however, that the names of
such symbol macros occupy the name space of variables, not the name space of
functions; just as one may have a function (or macro, or special form) and a
variable with the same name without interference, so one may have an ordinary
macro (or function, or special form) and a symbol macro with the same name. The
use of symbol-macrolet can therefore be shadowed by let or other constructs
that bind variables; symbol-macrolet does not substitute for all occurrences of
a var as a variable but only for those occurrences that would be construed as
references in the scope of a lexical binding of var as a variable. For example:

(symbol-macrolet ((pollyanna 'goody))
  (list pollyanna (let ((pollyanna 'two-shoes)) pollyanna)))
 => (goody two-shoes), not (goody goody)

One might think that 'goody simply replaces all occurrences of pollyanna, and
so the value of the let would be goody; but this is not so. A little reflection
shows that under this incorrect interpretation the body in expanded form would
be

(list 'goody (let (('goody 'two-shoes)) 'goody))

which is syntactically malformed. The correct expanded form is

(list 'goody (let ((pollyanna 'two-shoes)) pollyanna))

because the rebinding of pollyanna by the let form shadows the symbol macro
definition.

The expansion for each var is not evaluated at binding time but only after it
has replaced a reference to the var. The setf macro allows a symbol macro to be
used as a place, in which case its expansion is used; moreover, setq of a
variable that is really a symbol macro will be treated as if setf had been
used. The values of the last form are returned, or nil if there is no value.

See macroexpand and macroexpand-1; they will expand symbol macros as well as
ordinary macros.

Certain declarations before the body are handled in a peculiar manner; see
section 9.1.
[change_end]

-------------------------------------------------------------------------------

7.6. Conditionals

The traditional conditional construct in Lisp is cond. However, if is much
simpler and is directly comparable to conditional constructs in other
programming languages, so it is considered to be primitive in Common Lisp and
is described first. Common Lisp also provides the dispatching constructs case
and typecase, which are often more convenient than cond.

[Special Form]
if test then [else]

The if special form corresponds to the if-then-else construct found in most
algebraic programming languages. First the form test is evaluated. If the
result is not nil, then the form then is selected; otherwise the form else is
selected. Whichever form is selected is then evaluated, and if returns whatever
is returned by evaluation of the selected form.

(if test then else) == (cond (test then) (t else))

but if is considered more readable in some situations.

The else form may be omitted, in which case if the value of test is nil then
nothing is done and the value of the if form is nil. If the value of the if
form is important in this situation, then the and construct may be
stylistically preferable, depending on the context. If the value is not
important, but only the effect, then the when construct may be stylistically
preferable.

[Macro]
when test {form}*

(when test form1 form2 ... ) first evaluates test. If the result is nil, then
no form is evaluated, and nil is returned. Otherwise the forms constitute an
implicit progn and are evaluated sequentially from left to right, and the value
of the last one is returned.

(when p a b c) == (and p (progn a b c))
(when p a b c) == (cond (p a b c))
(when p a b c) == (if p (progn a b c) nil)
(when p a b c) == (unless (not p) a b c)

As a matter of style, when is normally used to conditionally produce some side
effects, and the value of the when form is normally not used. If the value is
relevant, then it may be stylistically more appropriate to use and or if.

[Macro]
unless test {form}*

(unless test form1 form2 ... ) first evaluates test. If the result is not nil,
then the forms are not evaluated, and nil is returned. Otherwise the forms
constitute an implicit progn and are evaluated sequentially from left to right,
and the value of the last one is returned.

(unless p a b c) == (cond ((not p) a b c))
(unless p a b c) == (if p nil (progn a b c))
(unless p a b c) == (when (not p) a b c)

As a matter of style, unless is normally used to conditionally produce some
side effects, and the value of the unless form is normally not used. If the
value is relevant, then it may be stylistically more appropriate to use if.

[Macro]
cond {(test {form}*)}*

A cond form has a number (possibly zero) of clauses, which are lists of forms.
Each clause consists of a test followed by zero or more consequents. For
example:

(cond (test-1 consequent-1-1 consequent-1-2 ...)
      (test-2)
      (test-3 consequent-3-1 ...)
      ... )

The first clause whose test evaluates to non-nil is selected; all other clauses
are ignored, and the consequents of the selected clause are evaluated in order
(as an implicit progn).

More specifically, cond processes its clauses in order from left to right. For
each clause, the test is evaluated. If the result is nil, cond advances to the
next clause. Otherwise, the cdr of the clause is treated as a list of forms, or
consequents; these forms are evaluated in order from left to right, as an
implicit progn. After evaluating the consequents, cond returns without
inspecting any remaining clauses. The cond special form returns the results of
evaluating the last of the selected consequents; if there were no consequents
in the selected clause, then the single (and necessarily non-null) value of the
test is returned. If cond runs out of clauses (every test produced nil, and
therefore no clause was selected), the value of the cond form is nil.

If it is desired to select the last clause unconditionally if all others fail,
the standard convention is to use t for the test. As a matter of style, it is
desirable to write a last clause (t nil) if the value of the cond form is to be
used for something. Similarly, it is in questionable taste to let the last
clause of a cond be a ``singleton clause''; an explicit t should be provided.
(Note moreover that (cond ... (x)) may behave differently from (cond ... (t x))
if x might produce multiple values; the former always returns a single value,
whereas the latter returns whatever values x returns. However, as a matter of
style it is preferable to obtain this behavior by writing (cond ... (t (values
x))), using the values function explicitly to indicate the discarding of any
excess values.) For example:

(setq z (cond (a 'foo) (b 'bar)))          ;Possibly confusing
(setq z (cond (a 'foo) (b 'bar) (t nil)))  ;Better
(cond (a b) (c d) (e))                     ;Possibly confusing
(cond (a b) (c d) (t e))                   ;Better
(cond (a b) (c d) (t (values e)))          ;Better (if one value
                                           ; needed)
(cond (a b) (c))                           ;Possibly confusing
(cond (a b) (t c))                         ;Better
(if a b c)                                 ;Also better

A Lisp cond form may be compared to a continued if-then-else as found in many
algebraic programming languages:

(cond (p ...)                            if p then ...
      (q ...)            roughly         else if q then ...
      (r ...)          corresponds       else if r then ...
      ...                   to           ...
      (t ...))                           else ...

[Macro]
case keyform {({({key}*) | key} {form}*)}*

case is a conditional that chooses one of its clauses to execute by comparing a
value to various constants, which are typically keyword symbols, integers, or
characters (but may be any objects). Its form is as follows:

(case keyform
  (keylist-1 consequent-1-1 consequent-1-2 ...)
  (keylist-2 consequent-2-1 ...)
  (keylist-3 consequent-3-1 ...)
  ...)

Structurally case is much like cond, and it behaves like cond in selecting one
clause and then executing all consequents of that clause. However, case differs
in the mechanism of clause selection.

The first thing case does is to evaluate the form keyform to produce an object
called the key object. Then case considers each of the clauses in turn. If key
is in the keylist (that is, is eql to any item in the keylist) of a clause, the
consequents of that clause are evaluated as an implicit progn; case returns
what was returned by the last consequent (or nil if there are no consequents in
that clause). If no clause is satisfied, case returns nil.

The keys in the keylists are not evaluated; literal key values must appear in
the keylists. It is an error for the same key to appear in more than one
clause; a consequence is that the order of the clauses does not affect the
behavior of the case construct.

Instead of a keylist, one may write one of the symbols t and otherwise. A
clause with such a symbol always succeeds and must be the last clause (this is
an exception to the order-independence of clauses). See also ecase and ccase,
each of which provides an implicit otherwise clause to signal an error if no
clause is satisfied.

If there is only one key for a clause, then that key may be written in place of
a list of that key, provided that no ambiguity results. Such a ``singleton
key'' may not be nil (which is confusable with (), a list of no keys), t,
otherwise, or a cons.

-------------------------------------------------------------------------------
Compatibility note: The Lisp Machine Lisp caseq construct uses eq for the
comparison. In Lisp Machine Lisp caseq therefore works for fixnums but not
bignums. The MacLisp caseq construct simply prohibits the use of bignums;
indeed, it permits only fixnums and symbols as clause keys. In the interest of
hiding the fixnum-bignum distinction, and for general language consistency,
case uses eql in Common Lisp.

The Interlisp selectq construct is similar to case.
-------------------------------------------------------------------------------

[Macro]
typecase keyform {(type {form}*)}*

typecase is a conditional that chooses one of its clauses by examining the type
of an object. Its form is as follows:

(typecase keyform
  (type-1 consequent-1-1 consequent-1-2 ...)
  (type-2 consequent-2-1 ...)
  (type-3 consequent-3-1 ...)
  ...)

Structurally typecase is much like cond or case, and it behaves like them in
selecting one clause and then executing all consequents of that clause. It
differs in the mechanism of clause selection.

The first thing typecase does is to evaluate the form keyform to produce an
object called the key object. Then typecase considers each of the clauses in
turn. The type that appears in each clause is a type specifier; it is not
evaluated but is a literal type specifier. The first clause for which the key
is of that clause's specified type is selected, the consequents of this clause
are evaluated as an implicit progn, and typecase returns what was returned by
the last consequent (or nil if there are no consequents in that clause). If no
clause is satisfied, typecase returns nil.

As for case, the symbol t or otherwise may be written for type to indicate that
the clause should always be selected. See also etypecase and ctypecase, each of
which provides an implicit otherwise clause to signal an error if no clause is
satisfied.

It is permissible for more than one clause to specify a given type,
particularly if one is a subtype of another; the earliest applicable clause is
chosen. Thus for typecase, unlike case, the order of the clauses may affect the
behavior of the construct. For example:

(typecase an-object
   (string ...)            ;This clause handles strings
   ((array t) ...)         ;This clause handles general arrays
   ((array bit) ...)       ;This clause handles bit arrays
   (array ...)             ;This handles all other arrays
   ((or list number) ...)  ;This handles lists and numbers
   (t ...))                ;This handles all other objects

A Common Lisp compiler may choose to issue a warning if a clause cannot be
selected because it is completely shadowed by earlier clauses.

-------------------------------------------------------------------------------

7.7. Blocks and Exits

The block and return-from constructs provide a structured lexical non-local
exit facility. At any point lexically within a block construct, a return-from
with the same name may be used to perform an immediate transfer of control that
exits from the block. In the most common cases this mechanism is more efficient
than the dynamic non-local exit facility provided by catch and throw, described
in section 7.11.

[Special Form]
block name {form}*

The block construct executes each form from left to right, returning whatever
is returned by the last form. If, however, a return or return-from form that
specifies the same name is executed during the execution of some form, then the
results specified by the return or return-from are immediately returned as the
value of the block construct, and execution proceeds as if the block had
terminated normally. In this, block differs from progn; the progn construct has
nothing to do with return.

The name is not evaluated; it must be a symbol. The scope of the name is
lexical; only a return or return-from textually contained in some form can exit
from the block. The extent of the name is dynamic. Therefore it is only
possible to exit from a given run-time incarnation of a block once, either
normally or by explicit return.

The defun form implicitly puts a block around the body of the function defined;
the block has the same name as the function. Therefore one may use return-from
to return prematurely from a function defined by defun.

The lexical scoping of the block name is fully general and has consequences
that may be surprising to users and implementors of other Lisp systems. For
example, the return-from in the following example actually does work in Common
Lisp as one might expect:

(block loser
   (catch 'stuff
      (mapcar #'(lambda (x) (if (numberp x)
                                (hairyfun x)
                                (return-from loser nil)))
              items)))

Depending on the situation, a return in Common Lisp may not be simple. A return
can break up catchers if necessary to get to the block in question. It is
possible for a ``closure'' created by function for a lambda-expression to refer
to a block name as long as the name is lexically apparent.

[Special Form]
return-from name [result]

return-from is used to return from a block or from such constructs as do and
prog that implicitly establish a block. The name is not evaluated and must be a
symbol. A block construct with the same name must lexically enclose the
occurrence of return-from; whatever the evaluation of result produces is
immediately returned from the block. (If the result form is omitted, it
defaults to nil. As a matter of style, this form ought to be used to indicate
that the particular value returned doesn't matter.)

The return-from form itself never returns and cannot have a value; it causes
results to be returned from a block construct. If the evaluation of result
produces multiple values, those multiple values are returned by the construct
exited.

[Macro]
return [result]

(return form) is identical in meaning to (return-from nil form); it returns
from a block named nil. Blocks established implicitly by iteration constructs
such as do are named nil, so that return will exit properly from such a
construct.

-------------------------------------------------------------------------------

7.8. Iteration

Common Lisp provides a number of iteration constructs. The loop construct
provides a trivial iteration facility; it is little more than a progn with a
branch from the bottom back to the top. The do and do* constructs provide a
general iteration facility for controlling the variation of several variables
on each cycle. For specialized iterations over the elements of a list or n
consecutive integers, dolist and dotimes are provided. The tagbody construct is
the most general, permitting arbitrary go statements within it. (The
traditional prog construct is a synthesis of tagbody, block, and let.) Most of
the iteration constructs permit statically defined non-local exits (see
return-from and return).

-------------------------------------------------------------------------------

   *  Indefinite Iteration
   *  General Iteration
   *  Simple Iteration Constructs
   *  Mapping
   *  The ``Program Feature''

-------------------------------------------------------------------------------

7.8.1. Indefinite Iteration

The loop construct is the simplest iteration facility. It controls no
variables, and simply executes its body repeatedly.

[Macro]
loop {form}*

Each form is evaluated in turn from left to right. When the last form has been
evaluated, then the first form is evaluated again, and so on, in a never-ending
cycle. The loop construct never returns a value. Its execution must be
terminated explicitly, using return or throw, for example.

loop, like most iteration constructs, establishes an implicit block named nil.
Thus return may be used to exit from a loop with specified results.

[old_change_begin]
A loop construct has this meaning only if every form is non-atomic (a list).
The case where some form is atomic is reserved for future extensions.

-------------------------------------------------------------------------------
Implementation note: There have been several proposals for a powerful iteration
mechanism to be called loop. One version is provided in Lisp Machine Lisp.
Implementors are encouraged to experiment with extensions to the loop syntax,
but users should be advised that in all likelihood some specific set of
extensions to loop will be adopted in a future revision of Common Lisp.
-------------------------------------------------------------------------------

[old_change_end]

[change_begin]
X3J13 voted in January 1989 (LOOP-FACILITY)   to include just such an extension
of loop. See chapter 26.
[change_end]

-------------------------------------------------------------------------------

7.8.2. General Iteration

In contrast to loop, do and do* provide a powerful and general mechanism for
repetitively recalculating many variables.

[Macro]

do ({(var [init [step]])}*)
   (end-test {result}*)
   {declaration}* {tag | statement}*
do* ({(var [init [step]])}*)
   (end-test {result}*)
   {declaration}* {tag | statement}*

The do special form provides a generalized iteration facility, with an
arbitrary number of ``index variables.'' These variables are bound within the
iteration and stepped in parallel in specified ways. They may be used both to
generate successive values of interest (such as successive integers) or to
accumulate results. When an end condition is met, the iteration terminates with
a specified value.

In general, a do loop looks like this:

(do ((var1 init1 step1)
     (var2 init2 step2)
     ...
     (varn initn stepn))
    (end-test . result)
  {declaration}*
  . tagbody)

A do* loop looks exactly the same except that the name do is replaced by do*.

The first item in the form is a list of zero or more index-variable specifiers.
Each index-variable specifier is a list of the name of a variable var, an
initial value init, and a stepping form step. If init is omitted, it defaults
to nil. If step is omitted, the var is not changed by the do construct between
repetitions (though code within the do is free to alter the value of the
variable by using setq).

An index-variable specifier can also be just the name of a variable. In this
case, the variable has an initial value of nil and is not changed between
repetitions. As a matter of style, it is recommended that an unadorned variable
name be written only when that variable will be stored into (such as by setq)
before its first use. If it is important that the initial value be nil rather
than some undefined value, then it is clearer to write out (varj nil) if the
initial value is intended to mean ``false,'' or (varj '()) if the initial value
is intended to be an empty list.

[change_begin]
X3J13 voted in January 1989 (VARIABLE-LIST-ASYMMETRY)   to regularize the
binding formats for do, do*, let, let*, prog, prog*, and compiler-let. In the
case of do and do* the first edition was inconsistent; the formal syntax fails
to reflect the fact that a simple variable name may appear, as described in the
preceding paragraph. The definitions should read

[Macro]

do ({var | (var [init [step]])}*)
   (end-test {result}*)
   {declaration}* {tag | statement}*
do* ({var | (var [init [step]])}*)
   (end-test {result}*)
   {declaration}* {tag | statement}*

for consistency with the reading of the first edition and the X3J13 vote.
[change_end]

Before the first iteration, all the init forms are evaluated, and each var is
bound to the value of its respective init. This is a binding, not an
assignment; when the loop terminates, the old values of those variables will be
restored. For do, all of the init forms are evaluated before any var is bound;
hence all the init forms may refer to the old bindings of all the variables
(that is, to the values visible before beginning execution of the do
construct). For do*, the first init form is evaluated, then the first var is
bound to that value, then the second init form is evaluated, then the second
var is bound, and so on; in general, the initj form can refer to the new
binding vark if k < j, and otherwise to the old binding of vark.

The second element of the loop is a list of an end-testing predicate form
end-test and zero or more result forms. This resembles a cond clause. At the
beginning of each iteration, after processing the variables, the end-test is
evaluated. If the result is nil, execution proceeds with the body of the do (or
do*) form. If the result is not nil, the result forms are evaluated in order as
an implicit progn,   and then do returns. do returns the results of evaluating
the last result form. If there are no result forms, the value of do is nil.
Note that this is not quite analogous to the treatment of clauses in a cond
form, because a cond clause with no result forms returns the (non-nil) result
of the test.

At the beginning of each iteration other than the first, the index variables
are updated as follows. All the step forms are evaluated, from left to right,
and the resulting values are assigned to the respective index variables. Any
variable that has no associated step form is not assigned to. For do, all the
step forms are evaluated before any variable is updated; the assignment of
values to variables is done in parallel, as if by psetq. Because all of the
step forms are evaluated before any of the variables are altered, a step form
when evaluated always has access to the old values of all the index variables,
even if other step forms precede it. For do*, the first step form is evaluated,
then the value is assigned to the first var, then the second step form is
evaluated, then the value is assigned to the second var, and so on; the
assignment of values to variables is done sequentially, as if by setq. For
either do or do*, after the variables have been updated, the end-test is
evaluated as described above, and the iteration continues.

If the end-test of a do form is nil, the test will never succeed. Therefore
this provides an idiom for ``do forever'': the body of the do is executed
repeatedly, stepping variables as usual. (The loop construct performs a ``do
forever'' that steps no variables.) The infinite loop can be terminated by the
use of return, return-from, go to an outer level, or throw. For example:

(do ((j 0 (+ j 1)))
    (nil)                        ;Do forever
  (format t "~%Input ~D:" j)
  (let ((item (read)))
    (if (null item) (return)     ;Process items until nil seen
        (format t "~&Output ~D: ~S" j (process item)))))

The remainder of the do form constitutes an implicit tagbody. Tags may appear
within the body of a do loop for use by go statements appearing in the body
(but such go statements may not appear in the variable specifiers, the
end-test, or the result forms). When the end of a do body is reached, the next
iteration cycle (beginning with the evaluation of step forms) occurs.

An implicit block named nil surrounds the entire do form. A return statement
may be used at any point to exit the loop immediately.

declare forms may appear at the beginning of a do body. They apply to code in
the do body, to the bindings of the do variables, to the init forms, to the
step forms, to the end-test, and to the result forms.

-------------------------------------------------------------------------------
Compatibility note: ``Old-style'' MacLisp do loops, that is, those of the form
(do var init step end-test . body), are not supported in Common Lisp. Such
old-style loops are considered obsolete and in any case are easily converted to
a new-style do with the insertion of three pairs of parentheses. In practice
the compiler can catch nearly all instances of old-style do loops because they
will not have a legal format anyway.
-------------------------------------------------------------------------------

Here are some examples of the use of do:

(do ((i 0 (+ i 1))     ;Sets every null element of a-vector to zero
     (n (length a-vector)))
    ((= i n))
  (when (null (aref a-vector i))
    (setf (aref a-vector i) 0)))

The construction

(do ((x e (cdr x))
     (oldx x x))
    ((null x))
  body)

exploits parallel assignment to index variables. On the first iteration, the
value of oldx is whatever value x had before the do was entered. On succeeding
iterations, oldx contains the value that x had on the previous iteration.

Very often an iterative algorithm can be most clearly expressed entirely in the
step forms of a do, and the body is empty. For example,

(do ((x foo (cdr x))
     (y bar (cdr y))
     (z '() (cons (f (car x) (car y)) z)))
    ((or (null x) (null y))
     (nreverse z)))

does the same thing as (mapcar #'f foo bar). Note that the step computation for
z exploits the fact that variables are stepped in parallel. Also, the body of
the loop is empty. Finally, the use of nreverse to put an accumulated do loop
result into the correct order is a standard idiom. Another example:

(defun list-reverse (list)
       (do ((x list (cdr x))
            (y '() (cons (car x) y)))
           ((endp x) y)))

Note the use of endp rather than null or atom to test for the end of a list;
this may result in more robust code.

As an example of nested loops, suppose that env holds a list of conses. The car
of each cons is a list of symbols, and the cdr of each cons is a list of equal
length containing corresponding values. Such a data structure is similar to an
association list but is divided into ``frames''; the overall structure
resembles a rib cage. A lookup function on such a data structure might be

(defun ribcage-lookup (sym ribcage)
       (do ((r ribcage (cdr r)))
           ((null r) nil)
         (do ((s (caar r) (cdr s))
              (v (cdar r) (cdr v)))
             ((null s))
           (when (eq (car s) sym)
             (return-from ribcage-lookup (car v))))))

(Notice the use of indentation in the above example to set off the bodies of
the do loops.)

A do loop may be explained in terms of the more primitive constructs block,
return, let, loop, tagbody, and psetq as follows:

(block nil
  (let ((var1 init1)
        (var2 init2)
        ...
        (varn initn))
    {declaration}*
    (loop (when end-test (return (progn . result)))
          (tagbody . tagbody)
          (psetq var1 step1
                 var2 step2
                 ...
                 varn stepn))))

do* is exactly like do except that the bindings and steppings of the variables
are performed sequentially rather than in parallel. It is as if, in the above
explanation, let were replaced by let* and psetq were replaced by setq.

-------------------------------------------------------------------------------

7.8.3. Simple Iteration Constructs

The constructs dolist and dotimes execute a body of code once for each value
taken by a single variable. They are expressible in terms of do, but capture
very common patterns of use.

Both dolist and dotimes perform a body of statements repeatedly. On each
iteration a specified variable is bound to an element of interest that the body
may examine. dolist examines successive elements of a list, and dotimes
examines integers from 0 to n-1 for some specified positive integer n.

The value of any of these constructs may be specified by an optional result
form, which if omitted defaults to the value nil.

The return statement may be used to return immediately from a dolist or dotimes
form, discarding any following iterations that might have been performed; in
effect, a block named nil surrounds the construct. The body of the loop is
implicitly a tagbody construct; it may contain tags to serve as the targets of
go statements. Declarations may appear before the body of the loop.

[Macro]

dolist (var listform [resultform])
       {declaration}* {tag | statement}*

dolist provides straightforward iteration over the elements of a list. First
dolist evaluates the form listform, which should produce a list. It then
executes the body once for each element in the list, in order, with the
variable var bound to the element. Then resultform (a single form, not an
implicit progn) is evaluated, and the result is the value of the dolist form.
(When the resultform is evaluated, the control variable var is still bound and
has the value nil.) If resultform is omitted, the result is nil.

(dolist (x '(a b c d)) (prin1 x) (princ " ")) => nil
   after printing ``a b c d '' (note the trailing space)

An explicit return statement may be used to terminate the loop and return a
specified value.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

[Macro]

dotimes (var countform [resultform])
        {declaration}* {tag | statement}*

dotimes provides straightforward iteration over a sequence of integers. The
expression (dotimes (var countform resultform) . progbody) evaluates the form
countform, which should produce an integer. It then performs progbody once for
each integer from zero (inclusive) to count (exclusive), in order, with the
variable var bound to the integer; if the value of countform is zero or
negative, then the progbody is performed zero times. Finally, resultform (a
single form, not an implicit progn) is evaluated, and the result is the value
of the dotimes form. (When the resultform is evaluated, the control variable
var is still bound and has as its value the number of times the body was
executed.) If resultform is omitted, the result is nil.

An explicit return statement may be used to terminate the loop and return a
specified value.

Here is an example of the use of dotimes in processing strings:

;;; True if the specified subsequence of the string is a
;;; palindrome (reads the same forwards and backwards).

(defun palindromep (string &optional
                           (start 0)
                           (end (length string)))
  (dotimes (k (floor (- end start) 2) t)
    (unless (char-equal (char string (+ start k))
                        (char string (- end k 1)))
      (return nil))))

(palindromep "Able was I ere I saw Elba") => t

(palindromep "A man, a plan, a canal-Panama!") => nil

(remove-if-not #'alpha-char-p     ;Remove punctuation
               "A man, a plan, a canal-Panama!")
   => "AmanaplanacanalPanama"

(palindromep
 (remove-if-not #'alpha-char-p
                "A man, a plan, a canal-Panama!")) => t

(palindromep
 (remove-if-not
   #'alpha-char-p
   "Unremarkable was I ere I saw Elba Kramer, nu?")) => t

(palindromep
 (remove-if-not
   #'alpha-char-p
   "A man, a plan, a cat, a ham, a yak,
                   a yam, a hat, a canal-Panama!")) => t

(palindromep
 (remove-if-not
   #'alpha-char-p
   "Ja-da, ja-da, ja-da ja-da jing jing jing")) => nil

Altering the value of var in the body of the loop (by using setq, for example)
will have unpredictable, possibly implementation-dependent results. A Common
Lisp compiler may choose to issue a warning if such a variable appears in a
setq.

-------------------------------------------------------------------------------
Compatbility note: The dotimes construct is the closest thing in Common Lisp to
the Interlisp rptq construct.
-------------------------------------------------------------------------------

See also do-symbols, do-external-symbols, and do-all-symbols.

-------------------------------------------------------------------------------

7.8.4. Mapping

Mapping is a type of iteration in which a function is successively applied to
pieces of one or more sequences. The result of the iteration is a sequence
containing the respective results of the function applications. There are
several options for the way in which the pieces of the list are chosen and for
what is done with the results returned by the applications of the function.

The function map may be used to map over any kind of sequence. The following
functions operate only on lists.

[Function]

mapcar function list &rest more-lists
maplist function list &rest more-lists
mapc function list &rest more-lists
mapl function list &rest more-lists
mapcan function list &rest more-lists
mapcon function list &rest more-lists

For each of these mapping functions, the first argument is a function and the
rest must be lists. The function must take as many arguments as there are
lists.

mapcar operates on successive elements of the lists. First the function is
applied to the car of each list, then to the cadr of each list, and so on.
(Ideally all the lists are the same length; if not, the iteration terminates
when the shortest list runs out, and excess elements in other lists are
ignored.) The value returned by mapcar is a list of the results of the
successive calls to the function. For example:

(mapcar #'abs '(3 -4 2 -5 -6)) => (3 4 2 5 6)
(mapcar #'cons '(a b c) '(1 2 3)) => ((a . 1) (b . 2) (c . 3))

maplist is like mapcar except that the function is applied to the lists and
successive cdr's of those lists rather than to successive elements of the
lists. For example:

(maplist #'(lambda (x) (cons 'foo x))
         '(a b c d))
   => ((foo a b c d) (foo b c d) (foo c d) (foo d))

(maplist #'(lambda (x) (if (member (car x) (cdr x)) 0 1)))
         '(a b a c d b c))
   => (0 0 1 0 1 1 1)
   ;An entry is 1 if the corresponding element of the input
   ; list was the last instance of that element in the input list.

mapl and mapc are like maplist and mapcar, respectively, except that they do
not accumulate the results of calling the function.

-------------------------------------------------------------------------------
Compatibility note: In all Lisp systems since Lisp 1.5, mapl has been called
map. In the chapter on sequences it is explained why this was a bad choice.
Here the name map is used for the far more useful generic sequence mapper, in
closer accordance with the computer science literature, especially the growing
body of papers on functional programming. Note that this remark, predating the
design of the Common Lisp Object System, uses the term ``generic'' in a generic
sense and not necessarily in the technical sense used by CLOS (see chapter 2).
-------------------------------------------------------------------------------

These functions are used when the function is being called merely for its side
effects rather than for its returned values. The value returned by mapl or mapc
is the second argument, that is, the first sequence argument.

mapcan and mapcon are like mapcar and maplist, respectively, except that they
combine the results of the function using nconc instead of list. That is,

(mapcon f x1 ... xn)
   == (apply #'nconc (maplist f x1 ... xn))

and similarly for the relationship between mapcan and mapcar. Conceptually,
these functions allow the mapped function to return a variable number of items
to be put into the output list. This is particularly useful for effectively
returning zero or one item:

(mapcan #'(lambda (x) (and (numberp x) (list x)))
        '(a 1 b c 3 4 d 5))
   => (1 3 4 5)

In this case the function serves as a filter; this is a standard Lisp idiom
using mapcan. (The function remove-if-not might have been useful in this
particular context, however.) Remember that nconc is a destructive operation,
and therefore so are mapcan and mapcon; the lists returned by the function are
altered in order to concatenate them.

Sometimes a do or a straightforward recursion is preferable to a mapping
operation; however, the mapping functions should be used wherever they
naturally apply because this increases the clarity of the code.

The functional argument to a mapping function must be acceptable to apply; it
cannot be a macro or the name of a special form. Of course, there is nothing
wrong with using a function that has &optional and &rest parameters as the
functional argument.

[change_begin]
X3J13 voted in June 1988 (FUNCTION-TYPE)   to allow the function to be only of
type symbol or function; a lambda-expression is no longer acceptable as a
functional argument. One must use the function special form or the abbreviation
#' before a lambda-expression that appears as an explicit argument form.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------

7.8.5. The ``Program Feature''

Lisp implementations since Lisp 1.5 have had what was originally called ``the
program feature,'' as if it were impossible to write programs without it! The
prog construct allows one to write in an Algol-like or Fortran-like
statement-oriented style, using go statements that can refer to tags in the
body of the prog. Modern Lisp programming style tends to use prog rather
infrequently. The various iteration constructs, such as do, have bodies with
the characteristics of a prog. (However, the ability to use go statements
within iteration constructs is very seldom called upon in practice.)

Three distinct operations are performed by prog: it binds local variables, it
permits use of the return statement, and it permits use of the go statement. In
Common Lisp, these three operations have been separated into three distinct
constructs: let, block, and tagbody. These three constructs may be used
independently as building blocks for other types of constructs.

[Special Form]
tagbody {tag | statement}*

The part of a tagbody after the variable list is called the body. An item in
the body may be a symbol or an integer, in which case it is called a tag, or an
item in the body may be a list, in which case it is called a statement.

Each element of the body is processed from left to right. A tag is ignored; a
statement is evaluated, and its results are discarded. If the end of the body
is reached, the tagbody returns nil.

If (go tag) is evaluated, control jumps to the part of the body labelled with
the tag.

-------------------------------------------------------------------------------
Compatibility note: The ``computed go'' feature of MacLisp is not supported.
The syntax of a computed go is idiosyncratic, and the feature is not supported
by Lisp Machine Lisp, NIL (New Implementation of Lisp), or Interlisp. The
computed go has been infrequently used in MacLisp anyway and is easily
simulated with no loss of efficiency by using a case statement each of whose
clauses performs a (non-computed) go.
-------------------------------------------------------------------------------

The scope of the tags established by a tagbody is lexical, and the extent is
dynamic. Once a tagbody construct has been exited, it is no longer legal to go
to a tag in its body. It is permissible for a go to jump to a tagbody that is
not the innermost tagbody construct containing that go; the tags established by
a tagbody will only shadow other tags of like name.

The lexical scoping of the go targets named by tags is fully general and has
consequences that may be surprising to users and implementors of other Lisp
systems. For example, the go in the following example actually does work in
Common Lisp as one might expect:

(tagbody
   (catch 'stuff
      (mapcar #'(lambda (x) (if (numberp x)
                                (hairyfun x)
                                (go lose)))
              items))
   (return)
 lose
   (error "I lost big!"))

Depending on the situation, a go in Common Lisp does not necessarily correspond
to a simple machine ``jump'' instruction. A go can break up catchers if
necessary to get to the target. It is possible for a ``closure'' created by
function for a lambda-expression to refer to a go target as long as the tag is
lexically apparent. See chapter 3 for an elaborate example of this.

[change_begin]
There are some holes in this specification (and that of go) that leave some
room for interpretation. For example, there is no explicit prohibition against
the same tag appearing more than once in the same tagbody body. Every
implementation I know of will complain in the compiler, if not in the
interpreter, if there is a go to such a duplicated tag; but some implementors
take the position that duplicate tags are permitted provided there is no go to
such a tag. (``If a tree falls in the forest, and there is no one there to hear
it, then no one needs to yell `Timber!''') Also, some implementations allow
objects other than symbols, integers, and lists in the body and typically
ignore them. Consequently, some programmers use redundant tags such as - for
formatting purposes, and strings as comments:

(defun dining-philosopher (j)
  (tagbody -
   think   (unless (hungry) (go think))
           -
           "Can't eat without chopsticks."
           (snatch (chopstick j))
           (snatch (chopstick (mod (+ j 1) 5)))
           -
   eat     (when (hungry)
             (mapc #'gobble-down
                   '(twice-cooked-pork kung-pao-chi-ding
                     wu-dip-har orange-flavor-beef
                     two-side-yellow-noodles twinkies))
             (go eat))
           -
           "Can't think with my neighbors' stomachs rumbling."
           (relinquish (chopstick j))
           (relinquish (chopstick (mod (+ j 1) 5)))
           -
           (if (happy) (go think)
               (become insurance-salesman))))

In certain implementations of Common Lisp they get away with it. Others abhor
what they view as an abuse of unintended ambiguity in the language
specification. For maximum portability, I advise users to steer clear of these
issues. Similarly, it is best to avoid using nil as a tag, even though it is a
symbol, because a few implementations treat nil as a list to be executed. To be
extra careful, avoid calling from within a tagbody a macro whose expansion
might not be a non-nil list; wrap such a call in (progn ...), or rewrite the
macro to return (progn ...) if possible.
[change_end]

[Macro]

prog ({var | (var [init])}*) {declaration}* {tag | statement}*
prog* ({var | (var [init])}*) {declaration}* {tag | statement}*

The prog construct is a synthesis of let, block, and tagbody, allowing bound
variables and the use of return and go within a single construct. A typical
prog construct looks like this:

(prog (var1 var2 (var3 init3) var4 (var5 init5))
      {declaration}*
      statement1
 tag1
      statement2
      statement3
      statement4
 tag2
      statement5
      ...
      )

The list after the keyword prog is a set of specifications for binding var1,
var2, etc., which are temporary variables bound locally to the prog. This list
is processed exactly as the list in a let statement: first all the init forms
are evaluated from left to right (where nil is used for any omitted init form),
and then the variables are all bound in parallel to the respective results. Any
declaration appearing in the prog is used as if appearing at the top of the let
body.

The body of the prog is executed as if it were a tagbody construct; the go
statement may be used to transfer control to a tag.

A prog implicitly establishes a block named nil around the entire prog
construct, so that return may be used at any time to exit from the prog
construct.

Here is a fine example of what can be done with prog:

(defun king-of-confusion (w)
  "Take a cons of two lists and make a list of conses.
   Think of this function as being like a zipper."
  (prog (x y z)     ;Initialize x, y, z to nil
        (setq y (car w) z (cdr w))
   loop
        (cond ((null y) (return x))
              ((null z) (go err)))
   rejoin
        (setq x (cons (cons (car y) (car z)) x))
        (setq y (cdr y) z (cdr z))
        (go loop)
   err
        (cerror "Will self-pair extraneous items"
                "Mismatch - gleep!   S" y)
        (setq z y)
        (go rejoin)))

which is accomplished somewhat more perspicuously by

(defun prince-of-clarity (w)
  "Take a cons of two lists and make a list of conses.
   Think of this function as being like a zipper."
  (do ((y (car w) (cdr y))
       (z (cdr w) (cdr z))
       (x '() (cons (cons (car y) (car z)) x)))
      ((null y) x)
    (when (null z)
      (cerror "Will self-pair extraneous items"
              "Mismatch - gleep!   S" y)
      (setq z y))))

The prog construct may be explained in terms of the simpler constructs block,
let, and tagbody as follows:

(prog variable-list {declaration}* . body)
   == (block nil (let variable-list {declaration}* (tagbody . body)))

The prog* special form is almost the same as prog. The only difference is that
the binding and initialization of the temporary variables is done sequentially,
so that the init form for each one can use the values of previous ones.
Therefore prog* is to prog as let* is to let. For example,

(prog* ((y z) (x (car y)))
       (return x))

returns the car of the value of z.

[change_begin]
I haven't seen prog used very much in the last several years. Apparently
splitting it into functional constituents (let, block, tagbody) has been a
success. Common Lisp programmers now tend to use whichever specific construct
is appropriate.
[change_end]

[Special Form]
go tag

The (go tag) special form is used to do a ``go to'' within a tagbody construct.
The tag must be a symbol or an integer; the tag is not evaluated. go transfers
control to the point in the body labelled by a tag eql to the one given. If
there is no such tag in the body, the bodies of lexically containing tagbody
constructs (if any) are examined as well. It is an error if there is no
matching tag lexically visible to the point of the go.

The go form does not ever return a value.

As a matter of style, it is recommended that the user think twice before using
a go. Most purposes of go can be accomplished with one of the iteration
primitives, nested conditional forms, or return-from. If the use of go seems to
be unavoidable, perhaps the control structure implemented by go should be
packaged as a macro definition.

-------------------------------------------------------------------------------

7.9. Structure Traversal and Side Effects

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
side effects during the course of a built-in operation that can execute
user-supplied code while traversing a data structure.

Consider the following example:

(let ((x '(apples peaches pumpkin pie)))
  (dolist (z x)
    (when (eq z 'peaches)
      (setf (cddr x) '(mango kumquat)))
    (format t " S " (car z))))

Depending on the details of the implementation of dolist, this bit of code
could easily print

apples peaches mango kumquat

(which is perhaps what was intended), but it might as easily print

apples peaches pumpkin pie

Here is a plausible implementation of dolist that produces the first result:

(defmacro dolist ((var listform &optional (resultform ''nil))
                  &body body)
  (let ((tailvar (gensym "DOLIST")))
    `(do ((,tailvar ,listform (cdr ,tailvar)))
         ((null ,tailvar) ,resultform)
       (let ((,var (car ,tailvar))) ,@body))

But here is a plausible implementation of dolist that produces the second
result:

(defmacro dolist ((var listform &optional (resultform ''nil))
                  &body body)
  (let ((tailvar (gensym "DOLIST")))
    `(do ((,tailvar ,listform))
         ((null ,tailvar) ,resultform)
       (let ((,var (pop ,tailvar))) ,@body))

The X3J13 recognizes and legitimizes varying implementation practices: in
general it is an error for code executed during a ``structure-traversing''
operation to destructively modify the structure in a way that might affect the
ongoing traversal operation. The committee identified in particular the
following special cases.

For list traversal operations, the cdr chain may not be destructively modified.

For array traversal operations, the array may not be adjusted (see
adjust-array) and its fill pointer, if any, may not be modified.

For hash table operations (such as with-hash-table-iterator and maphash), new
entries may not be added or deleted, except that the very entry being processed
by user code may be changed or deleted.

For package symbol operations (for example, with-package-iterator and
do-symbols), new symbols may not be interned in, nor symbols uninterned from,
the packages being traversed or any packages they use, except that the very
symbol being processed by user code may be uninterned.

X3J13 noted that this vote is intended to clarify restrictions on the use of
structure traversal operations that are not themselves inherently destructive;
for example, it applies to map and dolist. Destructive operators such as delete
require even more complicated restrictions and are addressed by a separate
proposal.

The X3J13 vote did not specify a complete list of the operations to which these
restrictions apply. Table 7-1 shows what I believe to be a complete list of
operations that traverse structures and take user code as a body (in the case
of macros) or as a functional argument (in the case of functions).

In addition, note that user code should not modify list structure that might be
undergoing interpretation by the evaluator, whether explicitly invoked via eval
or implicitly invoked, for example as in the case of a hook function (a
defstruct print function, the value of *evalhook* or *applyhook*, etc.) that
happens to be a closure of interpreted code. Similarly, defstruct print
functions and other hooks should not perform side effects on data structures
being printed or being processed by format, or on a string given to
make-string-input-stream. You get the idea; be sensible.

Note that an operation such as mapcar or dolist traverses not only cdr pointers
(in order to chase down the list) but also car pointers (in order to obtain the
elements themselves). The restriction against modification appears to apply to
all these pointers.



Table 7-1: Structure Traversal Operations Subject to Side Effect Restrictions
-----------------------------------------------------------------------------
adjoin                   maphash                 reduce
assoc                    mapl                    remove
assoc-if                 maplist                 remove-duplicates
assoc-if-not             member                  remove-if
count                    member-if               remove-if-not
count-if                 member-if-not           search
count-if-not             merge                   set-difference
delete                   mismatch                set-exclusive-or
delete-duplicates        nintersection           some
delete-if                notany                  sort
delete-if-not            notevery                stable-sort
do-all-symbols           nset-difference         sublis
do-external-symbols      nset-exclusive-or       subsetp
do-symbols               nsublis                 subst
dolist                   nsubst                  subst-if
eval                     nsubst-if               subst-if-not
every                    nsubst-if-not           substitute
find                     nsubstitute             substitute-if
find-if                  nsubstitute-if          substitute-if-not
find-if-not              nsubstitute-if-not      tree-equal
intersection             nunion                  union
certain loop clauses     position                with-hash-table-iterator
map                      position-if             with-input-from-string
mapc                     position-if-not         with-output-to-string
mapcan                   rassoc                  with-package-iterator
mapcar                   rassoc-if
mapcon                   rassoc-if-not
-----------------------------------------------------------------------------

[change_end]

-------------------------------------------------------------------------------

7.10. Multiple Values

Ordinarily the result of calling a Lisp function is a single Lisp object.
Sometimes, however, it is convenient for a function to compute several objects
and return them. Common Lisp provides a mechanism for handling multiple values
directly. This mechanism is cleaner and more efficient than the usual tricks
involving returning a list of results or stashing results in global variables.

-------------------------------------------------------------------------------

   *  Constructs for Handling Multiple Values
   *  Rules Governing the Passing of Multiple Values

-------------------------------------------------------------------------------

7.10.1. Constructs for Handling Multiple Values

Normally multiple values are not used. Special forms are required both to
produce multiple values and to receive them. If the caller of a function does
not request multiple values, but the called function produces multiple values,
then the first value is given to the caller and all others are discarded; if
the called function produces zero values, then the caller gets nil as a value.

The primary primitive for producing multiple values is values, which takes any
number of arguments and returns that many values. If the last form in the body
of a function is a values with three arguments, then a call to that function
will return three values. Other special forms also produce multiple values, but
they can be described in terms of values. Some built-in Common Lisp functions,
such as floor, return multiple values; those that do are so documented.

The special forms and macros for receiving multiple values are as follows:

multiple-value-list
multiple-value-call
multiple-value-prog1
multiple-value-bind
multiple-value-setq

These specify a form to evaluate and an indication of where to put the values
returned by that form.

[Function]
values &rest args

All of the arguments are returned, in order, as values. For example:

(defun polar (x y)
  (values (sqrt (+ (* x x) (* y y))) (atan y x)))

(multiple-value-bind (r theta) (polar 3.0 4.0)
  (vector r theta))
   => #(5.0 0.9272952)

The expression (values) returns zero values. This is the standard idiom for
returning no values from a function.

Sometimes it is desirable to indicate explicitly that a function will return
exactly one value. For example, the function

(defun foo (x y)
  (floor (+ x y) y))

will return two values because floor returns two values. It may be that the
second value makes no sense, or that for efficiency reasons it is desired not
to compute the second value. The values function is the standard idiom for
indicating that only one value is to be returned, as shown in the following
example.

(defun foo (x y)
  (values (floor (+ x y) y)))

This works because values returns exactly one value for each of its argument
forms; as for any function call, if any argument form to values produces more
than one value, all but the first are discarded.

There is absolutely no way in Common Lisp for a caller to distinguish between
returning a single value in the ordinary manner and returning exactly one
``multiple value.'' For example, the values returned by the expressions (+ 1 2)
and (values (+ 1 2)) are identical in every respect: the single value 3.

[Constant]
multiple-values-limit

The value of multiple-values-limit is a positive integer that is the upper
exclusive bound on the number of values that may be returned from a function.
This bound depends on the implementation but will not be smaller than 20.
(Implementors are encouraged to make this limit as large as practicable without
sacrificing performance.) See lambda-parameters-limit and call-arguments-limit.

[Function]
values-list list

All of the elements of list are returned as multiple values. For example:

(values-list (list a b c)) == (values a b c)

In general,

(values-list list) == (apply #'values list)

but values-list may be clearer or more efficient.

[Macro]
multiple-value-list form

multiple-value-list evaluates form and returns a list of the multiple values it
returned. For example:

(multiple-value-list (floor -3 4)) => (-1 1)

multiple-value-list and values-list are therefore inverses of each other.

[Special Form]
multiple-value-call function {form}*

multiple-value-call first evaluates function to obtain a function and then
evaluates all of the forms. All the values of the forms are gathered together
(not just one value from each) and are all given as arguments to the function.
The result of multiple-value-call is whatever is returned by the function. For
example:

(+ (floor 5 3) (floor 19 4))
   == (+ 1 4) => 5
(multiple-value-call #'+ (floor 5 3) (floor 19 4))
   == (+ 1 2 4 3) => 10
(multiple-value-list form) == (multiple-value-call #'list form)

[Special Form]
multiple-value-prog1 form {form}*

multiple-value-prog1 evaluates the first form and saves all the values produced
by that form. It then evaluates the other forms from left to right, discarding
their values. The values produced by the first form are returned by
multiple-value-prog1. See prog1, which always returns a single value.

[Macro]

multiple-value-bind ({var}*) values-form
                      {declaration}* {form}*

The values-form is evaluated, and each of the variables var is bound to the
respective value returned by that form. If there are more variables than values
returned, extra values of nil are given to the remaining variables. If there
are more values than variables, the excess values are simply discarded. The
variables are bound to the values over the execution of the forms, which make
up an implicit progn. For example:

(multiple-value-bind (x) (floor 5 3) (list x)) => (1)
(multiple-value-bind (x y) (floor 5 3) (list x y)) => (1 2)
(multiple-value-bind (x y z) (floor 5 3) (list x y z))
   => (1 2 nil)

[Macro]
multiple-value-setq variables form

The variables must be a list of variables. The form is evaluated, and the
variables are set (not bound) to the values returned by that form. If there are
more variables than values returned, extra values of nil are assigned to the
remaining variables. If there are more values than variables, the excess values
are simply discarded.

-------------------------------------------------------------------------------
Compatibility note: In Lisp Machine Lisp this is called multiple-value. The
added clarity of the name multiple-value-setq in Common Lisp was deemed worth
the incompatibility with Lisp Machine Lisp.
-------------------------------------------------------------------------------

multiple-value-setq always returns a single value, which is the first value
returned by form, or nil if form produces zero values.

[change_begin]
X3J13 voted in March 1989 (SYMBOL-MACROLET-SEMANTICS)   to specify that if any
var refers not to an ordinary variable but to a binding made by
symbol-macrolet, then that var is handled as if setq were used to assign the
appropriate value to it.

[Macro]
nth-value n form

X3J13 voted in January 1989 (NTH-VALUE)   to add a new macro named nth-value.
The argument forms n and form are both evaluated. The value of n must be a
non-negative integer, and the form may produce any number of values. The
integer n is used as a zero-based index into the list of values. Value n of the
form is returned as the single value of the nth-value form; nil is returned if
the form produces no more than n values.

As an example, mod could be defined as

(defun mod (number divisor)
  (nth-value 1 (floor number divisor)))

Value number 1 is the second value returned by floor, the first value being
value number 0.

One could define nth-value simply as

(defmacro nth-value (n form)
  `(nth ,n (multiple-value-list ,form)))

but the clever implementor will doubtless find an implementation technique for
nth-value that avoids constructing an intermediate list of all the values of
the form.
[change_end]

Common Lisp the Language, 2nd Edition BR>
-------------------------------------------------------------------------------

7.10.2. Rules Governing the Passing of Multiple Values

It is often the case that the value of a special form or macro call is defined
to be the value of one of its subforms. For example, the value of a cond is the
value of the last form in the selected clause.

In most such cases, if the subform produces multiple values, then the original
form will also produce all of those values. This passing back of multiple
values of course has no effect unless eventually one of the special forms for
receiving multiple values is reached.

To be explicit, multiple values can result from a special form under precisely
these circumstances:

Evaluation and application

   *  eval returns multiple values if the form given it to evaluate produces
     multiple values.

   *  apply, funcall, and multiple-value-call pass back multiple values from
     the function applied or called.

Implicit progn contexts

   *  The special form progn passes back multiple values resulting from
     evaluation of the last subform. Other situations referred to as ``implicit
     progn,'' where several forms are evaluated and the results of all but the
     last form are discarded, also pass back multiple values from the last
     form. These situations include the body of a lambda-expression, in
     particular those constructed by defun, defmacro, and deftype. Also
     included are bodies of the constructs eval-when, progv, let, let*, when,
     unless, block, multiple-value-bind, and catch, as well as clauses in such
     conditional constructs as case, typecase, ecase, etypecase, ccase, and
     ctypecase.

[change_begin]
X3J13 has voted to add many new constructs to the language that contain
implicit progn contexts. I won't attempt to list them all here. Of particular
interest, however, is locally, which may be regarded as simply a version of
progn that permits declarations before its body. This provides a useful
building block for constructing macros that permit declarations (but not
documentation strings) before their bodies and pass back any multiple values
produced by the last sub-form of a body. (If a body can contain a documentation
string, most likely lambda is the correct building block to use.)
[change_end]

Conditional constructs

   *  if passes back multiple values from whichever subform is selected (the
     then form or the else form).

   *  and and or pass back multiple values from the last subform but not from
     subforms other than the last.

   *  cond passes back multiple values from the last subform of the implicit
     progn of the selected clause. If, however, the clause selected is a
     singleton clause, then only a single value (the non-nil predicate value)
     is returned. This is true even if the singleton clause is the last clause
     of the cond. It is not permitted to treat a final clause (x) as being the
     same as (t x) for this reason; the latter passes back multiple values from
     the form x.

Returning from a block

   *  The block construct passes back multiple values from its last subform
     when it exits normally. If return-from (or return) is used to terminate
     the block prematurely, then return-from passes back multiple values from
     its subform as the values of the terminated block. Other constructs that
     create implicit blocks, such as do, dolist, dotimes, prog, and prog*, also
     pass back multiple values specified by return-from (or return).

   *  do passes back multiple values from the last form of the exit clause,
     exactly as if the exit clause were a cond clause. Similarly, dolist and
     dotimes pass back multiple values from the resultform if that is executed.
     These situations are all examples of implicit uses of return-from.

Throwing out of a catch

   *  The catch construct returns multiple values if the result form in a throw
     exiting from such a catch produces multiple values.

Miscellaneous situations

   *  multiple-value-prog1 passes back multiple values from its first subform.
     However, prog1 always returns a single value.

   *  unwind-protect returns multiple values if the form it protects returns
     multiple values.

   *  the returns multiple values if the form it contains returns multiple
     values.

Among special forms that never pass back multiple values are prog1, prog2,
setq, and multiple-value-setq. The conventional way to force only one value to
be returned from a form x is to write (values x).

The most important rule about multiple values is: No matter how many values a
form produces, if the form is an argument form in a function call, then exactly
one value (the first one) is used.

For example, if you write (cons (floor x)), then cons will always receive
exactly one argument (which is of course an error), even though floor returns
two values. To pass both values from floor to cons, one must write something
like (multiple-value-call #'cons (floor x)). In an ordinary function call, each
argument form produces exactly one argument; if such a form returns zero
values, nil is used for the argument, and if more than one value, all but the
first are discarded. Similarly, conditional constructs such as if that test the
value of a form will use exactly one value, the first one, from that form and
discard the rest; such constructs will use nil as the test value if zero values
are returned.

-------------------------------------------------------------------------------

7.11. Dynamic Non-Local Exits

Common Lisp provides a facility for exiting from a complex process in a
non-local, dynamically scoped manner. There are two classes of special forms
for this purpose, called catch forms and throw forms, or simply catches and
throws. A catch form evaluates some subforms in such a way that, if a throw
form is executed during such evaluation, the evaluation is aborted at that
point and the catch form immediately returns a value specified by the throw.
Unlike block and return (section 7.7), which allow for exiting a block form
from any point lexically within the body of the block, the catch/throw
mechanism works even if the throw form is not textually within the body of the
catch form. The throw need only occur within the extent (time span) of the
evaluation of the body of the catch. This is analogous to the distinction
between dynamically bound (special) variables and lexically bound (local)
variables.

[Special Form]
catch tag {form}*

The catch special form serves as a target for transfer of control by throw. The
form tag is evaluated first to produce an object that names the catch; it may
be any Lisp object. A catcher is then established with the object as the tag.
The forms are evaluated as an implicit progn, and the results of the last form
are returned, except that if during the evaluation of the forms a throw should
be executed such that the tag of the throw matches (is eq to) the tag of the
catch and the catcher is the most recent outstanding catcher with that tag,
then the evaluation of the forms is aborted and the results specified by the
throw are immediately returned from the catch expression. The catcher
established by the catch expression is disestablished just before the results
are returned.

The tag is used to match throws with catches. (catch 'foo form) will catch a
(throw 'foo form) but not a (throw 'bar form). It is an error if throw is done
when there is no suitable catch ready to catch it.

Catch tags are compared using eq, not eql; therefore numbers and characters
should not be used as catch tags.

-------------------------------------------------------------------------------
Compatibility note: The name catch comes from MacLisp, but the syntax of catch
in Common Lisp is different. The MacLisp syntax was (catch form tag), where the
tag was not evaluated.
-------------------------------------------------------------------------------


[Special Form]
unwind-protect protected-form {cleanup-form}*

Sometimes it is necessary to evaluate a form and make sure that certain side
effects take place after the form is evaluated; a typical example is

(progn (start-motor)
       (drill-hole)
       (stop-motor))

The non-local exit facility of Common Lisp creates a situation in which the
above code won't work, however: if drill-hole should do a throw to a catch that
is outside of the progn form (perhaps because the drill bit broke), then
(stop-motor) will never be evaluated (and the motor will presumably be left
running). This is particularly likely if drill-hole causes a Lisp error and the
user tells the error-handler to give up and abort the computation. (A possibly
more practical example might be

(prog2 (open-a-file)
       (process-file)
       (close-the-file))

where it is desired always to close the file when the computation is terminated
for whatever reason. This case is so important that Common Lisp provides the
special form with-open-file for this purpose.)

In order to allow the example hole-drilling program to work, it can be
rewritten using unwind-protect as follows:

;; Stop the motor no matter what (even if it failed to start).

(unwind-protect
  (progn (start-motor)
         (drill-hole))
  (stop-motor))

If drill-hole does a throw that attempts to quit out of the unwind-protect,
then (stop-motor) will be executed.

This example assumes that it is correct to call stop-motor even if the motor
has not yet been started. Remember that an error or interrupt may cause an exit
even before any initialization forms have been executed. Any state restoration
code should operate correctly no matter where in the protected code an exit
occurred. For example, the following code is not correct:

(unwind-protect
  (progn (incf *access-count*)
         (perform-access))
  (decf *access-count*))

If an exit occurs before completion of the incf operation the decf operation
will be executed anyway, resulting in an incorrect value for *access-count*.
The correct way to code this is as follows:

(let ((old-count *access-count*))
  (unwind-protect
    (progn (incf *access-count*)
           (perform-access))
    (setq *access-count* old-count)))

As a general rule, unwind-protect guarantees to execute the cleanup-forms
before exiting, whether it terminates normally or is aborted by a throw of some
kind. (If, however, an exit occurs during execution of the cleanup-forms, no
special action is taken. The cleanup-forms of an unwind-protect are not
protected by that unwind-protect, though they may be protected if that
unwind-protect occurs within the protected form of another unwind-protect.)
unwind-protect returns whatever results from evaluation of the protected-form
and discards all the results from the cleanup-forms.

It should be emphasized that unwind-protect protects against all attempts to
exit from the protected form, including not only ``dynamic exit'' facilities
such as throw but also ``lexical exit'' facilities such as go and return-from.
Consider this situation:

(tagbody
  (let ((x 3))
    (unwind-protect
      (if (numberp x) (go out))
      (print x)))
 out
  ...)

When the go is executed, the call to print is executed first, and then the
transfer of control to the tag out is completed.

[change_begin]
X3J13 voted in March 1989 (EXIT-EXTENT)   to clarify the interaction of
unwind-protect with constructs that perform exits.

Let an exit be a point out of which control can be transferred. For a throw the
exit is the matching catch; for a return-from the exit is the corresponding
block. For a go the exit is the statement within the tagbody (the one to which
the target tag belongs) which is being executed at the time the go is
performed.

The extent of an exit is dynamic; it is not indefinite. The extent of an exit
begins when the corresponding form (catch, block, or tagbody statement) is
entered. When the extent of an exit has ended, it is no longer legal to return
from it.

Note that the extent of an exit is not the same thing as the scope or extent of
the designator by which the exit is identified. For example, a block name has
lexical scope but the extent of its exit is dynamic. The extent of a catch tag
could differ from the extent of the exit associated with the catch (which is
exactly what is at issue here). The difference matters when there are transfers
of control from the cleanup clauses of an unwind-protect.

When a transfer of control out of an exit is initiated by throw, return-from,
or go, a variety of events occur before the transfer of control is complete:

   *  The cleanup clauses of any intervening unwind-protect clauses are
     evaluated.
   *  Intervening dynamic bindings of special variables and catch tags are
     undone.
   *  Intervening exits are abandoned, that is, their extent ends and it is no
     longer legal to attempt to transfer control from them.
   *  The extent of the exit being invoked ends.
   *  Control is finally passed to the target.

The first edition left the order of these events in some doubt. The
implementation note for throw hinted that the first two processes are
interwoven, but it was unclear whether it is permissible for an implementation
to abandon all intervening exits before processing any intervening
unwind-protect cleanup clauses.

The clarification adopted by X3J13 is as follows. Intervening exits are
abandoned as soon as the transfer of control is initiated; in the case of a
throw, this occurs at the beginning of the ``second pass'' mentioned in the
implementation note. It is an error to attempt a transfer of control to an exit
whose dynamic extent has ended.

Next the evaluation of unwind-protect cleanup clauses and the undoing of
dynamic bindings and catch tags are performed together, in the order
corresponding to the reverse of the order in which they were established. The
effect of this is that the cleanup clauses of an unwind-protect will see the
same dynamic bindings of variables and catch tags as were visible when the
unwind-protect was entered. (However, some of those catch tags may not be
useable because they correspond to abandoned exit points.)

Finally control is transferred to the originally invoked exit and
simultaneously that exit is abandoned.

The effect of this specification is that once a program has attempted to
transfer control to a particular exit, an unwind-protect cleanup form cannot
step in and decide to transfer control to a more recent (nested) exit, blithely
forgetting the original exit request. However, a cleanup form may restate the
request to transfer to the same exit that started the cleanup process.

Here is an example based on a nautical metaphor. The function gently moves an
oar in the water with low force, but if an oar gets stuck, the caller will
catch a crab. The function row takes a boat, an oar-stroking function, a
stream, and a count; an oar is constructed for the boat and stream and the
oar-stroking function is called :count times. The function life rows a
particular boat. Merriment follows, except that if the oarsman is winded he
must stop to catch his breath.

(defun gently (oar)
  (stroke oar :force 0.5)
  (when (stuck oar)
    (throw 'crab nil)))

(defun row (boat stroke-fn stream &key count)
  (let ((oar (make-oar boat stream)))
    (loop repeat count do (funcall stroke-fn oar))))

(defun life ()
  (catch 'crab
    (catch 'breath
      (unwind-protect
        (row *your-boat* #'gently *query-io* :count 3))
        (when (winded) (throw 'breath nil)))
      (loop repeat 4 (set-mode :merry))
      (dream))))

Suppose that the oar gets stuck, causing gently to call throw with the tag
crab. The program is then committed to exiting from the outer catch (the one
with the tag crab). As control breaks out of the unwind-protect form, the
winded test is executed. Suppose it is true; then another call to throw occurs,
this time with the tag breath. The inner catch (the one with the tag breath)
has been abandoned as a result of the first throw operation (still in
progress). The clarification voted by X3J13 specifies that the program is in
error for attempting to transfer control to an abandoned exit point. To put it
in terms of the example: once you have begun to catch a crab, you cannot rely
on being able to catch your breath.

Implementations may support longer extents for exits than is required by this
specification, but portable programs may not rely on such extended extents.

(This specification is somewhat controversial. An alternative proposal was that
the abandoning of exits should be lumped in with the evaluation of
unwind-protect cleanup clauses and the undoing of dynamic bindings and catch
tags, performing all in reverse order of establishment. X3J13 agreed that this
approach is theoretically cleaner and more elegant but also more stringent and
of little additional practical use. There was some concern that a more
stringent specification might be a great added burden to some implementors and
would achieve only a small gain for users.)
[change_end]

[Special Form]
throw tag result

The throw special form transfers control to a matching catch construct. The tag
is evaluated first to produce an object called the throw tag; then the result
form is evaluated, and its results are saved (if the result form produces
multiple values, then all the values are saved). The most recent outstanding
catch whose tag matches the throw tag is exited; the saved results are returned
as the value(s) of the catch. A catch matches only if the catch tag is eq to
the throw tag.

In the process, dynamic variable bindings are undone back to the point of the
catch, and any intervening unwind-protect cleanup code is executed. The result
form is evaluated before the unwinding process commences, and whatever results
it produces are returned from the catch.

If there is no outstanding catcher whose tag matches the throw tag, no
unwinding of the stack is performed, and an error is signalled. When the error
is signalled, the outstanding catchers and the dynamic variable bindings are
those in force at the point of the throw.

-------------------------------------------------------------------------------
Implementation note: These requirements imply that throwing should typically
make two passes over the control stack. In the first pass it simply searches
for a matching catch. In this search every catch must be considered, but every
unwind-protect should be ignored. On the second pass the stack is actually
unwound, one frame at a time, undoing dynamic bindings and outstanding
unwind-protect constructs in reverse order of creation until the matching catch
is reached.
-------------------------------------------------------------------------------
Compatibility note: The name throw comes from MacLisp, but the syntax of throw
in Common Lisp is different. The MacLisp syntax was (throw form tag), where the
tag was not evaluated.
-------------------------------------------------------------------------------